1386:回転配列の最小数@jobdu

タイトル1386:回転配列の最小数値
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:2738
解決:613
タイトルの説明:
1つの配列の最初のいくつかの要素を配列の末尾に運び、配列の回転と呼ぶ.増分ソートされた配列の回転を入力し、回転配列の最小要素を出力します.例えば、配列{3,4,5,1,2}は{1,2,3,4,5}の回転であり、この配列の最小値は1である.
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力された最初の動作の整数n(1<=n<=1000000):回転配列を表す要素の数.
入力された2行目はn個の整数を含み、各整数aの範囲は(1<=a<=1億円)である.
出力:
各テストケースに対応し、
回転配列の最小要素を出力します.
サンプル入力:

53 4 5 1 2

サンプル出力:

1

ポイントは3つのケースに分けて、要素が等しい場合は順番で検索するしかありません.そうしない場合は二分法で検索できます.
Javaは前の3つしか通らないので、タイムアウトします.C++で書けば大丈夫です.
全部で5つのケースがあり、3つ通過したが、総時間はタイムアウトした.

import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;


public class S8 {

	public static void main(String[] args) throws FileNotFoundException {
		BufferedInputStream in = new BufferedInputStream(new FileInputStream("S8.in"));
		System.setIn(in);
		Scanner cin = new Scanner(System.in);
		
		while (cin.hasNextInt()) {
			int n = cin.nextInt();
			int[] buf = new int[n];
			for(int i=0; i<n; i++){
				buf[i] = cin.nextInt();
			}
			System.out.println(findMin(buf));
		}
	}
	
	public static int findMin(int[] buf){
		int left = 0, right = buf.length-1;
		
		while(left <= right){
			if(right-left == 1){
				return Math.min(buf[left], buf[right]);
			}
			int mid = left + (right-left)/2;
			if(buf[mid]==buf[left] && buf[mid]==buf[right]){	// mid left right ， 
				int min = buf[left];
				for(int i=left; i<=right; i++){
					min = Math.min(min, buf[i]);
				}
				return min;
			}
			if(buf[mid] <= buf[right]){				// mid ， mid 
				right = mid;
			}
			else if(buf[mid] >= buf[left]){		// mid ， mid 
				left = mid;
			}
		}
		
		return -1;
	}
	

}