SearchInRotatedSortedArray.java

/*https://blog.csdn.net/ojshilu/article/details/17485787
 * 循环有序数组：

指的是，将一个有序数组循环左/右移动若干距离之后变成的数组。如，[1,2,3,4,5]循环右移3位，就成为[4,5,1,2,3]。该数组的特点是，其中包含着一个转折点。
转折点左右两侧的子数组都是有序的，并且左侧的子数组整体都比右侧的子数组大。

HINT:
1. 找到转折点在中间的哪一侧
 * */
public class SearchInRotatedSortedArray {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	public int search(int A[], int n, int target) {
		int left = 0;
		int right = A.length - 1;
		
		while(left<=right) {
			int mid = left + ((right-left)/2);
			if(A[mid] == target) {
				return mid;
			}
			
			if(A[left] <= A[mid]) {//转折点在右半边，左半边是单调递增的
				if(A[left] <= target && target < A[mid]) {
					//target in left side
					right = mid - 1;
				}else {
					left = mid + 1;
				}
			}else {
				//转折点在左半边
				if(A[mid] < target && target <= A[right]) {
					left = mid + 1;
				}else {
					right = mid - 1;
				}
			}
		}
		return -1;
	}

}