二分查找进阶——循环有序数组查找

（此题出自LeetCode）

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

题目大意是给定一个循环有序数组，让你查找其中的某个元素。

最开始想到的当然是暴力求解了，即整个数组遍历一遍。当然这样效率不高。既然这个数组是有序的，我们应该尝试着用其他方法解决它，比如今天的二分查找。

令人头疼的当然是如何确定二分查找的边界了！

int search(int* nums, int numsSize, int target)
{
	int first = 0;
	int last = numsSize - 1;

	while (first <= last) {
		int mid = (last - first) / 2 + first;
		if (*(nums + mid) == target)								//找到target
			return mid;
		else if (*(nums + first) <= *(nums + mid)) {				
			if (*(nums + first) <= target && target < *(nums + mid))
				last = mid - 1;
			else
				first = mid + 1;
		}
		else {														
			if (*(nums + mid) < target && target <= *(nums + last))
				first = mid + 1;
			else
				last = mid - 1;
		}
	}
	return -1;															//未找到
}

由于数组是循环有序的，并且每次求取的mid位置不确定，所以要进一步判断要查找的数在不在当前的 [first,mid] 或是 [mid,right] 区间里，进而才能确定下一步的边界。

只要弄清楚了边界是如何确定的，这道题就迎刃而解了！