Cracking the coding interview--Q9.3

題目

原文：

Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order.
EXAMPLE:
Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
Output: 8 (the index of 5 in the array)

譯文：

給一個長度為n的有序整型數組，但它已經被旋轉了未知次，給一個O(log n)的算法在這個數組中找出一個元素，你可以假設這個數組的初始排列是增序的。

例如：

輸入：在數組(15 16 19 20 25 1 3 4 5 7 10 14)中找出5

輸出：8(5在數組中的下標為8)

解答

首先要理解這個數組是有序的，但被旋轉過了，也就是說，數組部分是有序的；然後題目要求是O(log n)的算法，顯然可以用到二分查找法，但數組部分有序，即前面一段有序,後面一段有序，且前面那段的數要大於等於後面那段的數(本題遞增序列),所以首先需要判斷a[mid]是落在前半段還是後半段，假如a[mid]落在前半段(即a[mid]>=a[low])，這時如果所求值value是位於a[low]和a[mid]之間，則更新high = mid - 1；否則更新low = mid + 1。假如a[mid]落在後半段 (即a[mid]

class Q9_3{
	public static int search(int[] a,int fromIndex,int toIndex,int value){
		int low=fromIndex;
		int high=toIndex-1;
		while(low<=high){
			int mid=(low+high)>>>1;
		/*	int midVal=a[mid];
			if(a[low]value)
					high=mid-1;
				else if(midVal<)
			}*/
			if(a[mid]==value) return mid;
			if(a[mid]>=a[low]){
				if(value=a[low])
					high=mid-1;
				else
					low=mid+1;
			}else{
				if(value<=a[high]&&value>a[mid])
					low=mid+1;
				else
					high=mid-1;
			}
		}
		return -1;
	}
	public static void main(String[] args){
		int[] a={
        	15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14
    	};
    	System.out.println(search(a,0,12,5));
	}
}