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.

分析：已经排序的数组从某个点翻转了，假设数组中没有重复的元素，顺序查找当然可以，但是要利用有已有的排序。那么只有在二分查找的基础上下功夫了。具体思路是，数组中的左右的数组必有一个有序，那么我们就只处理有序的那一部分，如果目标元素在这个有序的部分，那么就把范围定位到这部分，直接二分查找即可。如果不在，继续缩小范围，直到将元素定位到有序的那部分。

代码：

class Solution{
public:
	int search(int A[], int n, int target) {
		int first =0 ;int last = n;
		while(first != last){
			int mid = (first + last)/2;
			if (A[mid] == target){
				return mid;
			}
			if (A[first] <= A[mid]){ //first到mid之间元素内有序，那么就在该段内尝试查找
				//判断target是否在范围之内
				if (A[first]<=target && target < A[mid]){
					last = mid;
				}else{
					first = mid + 1;
				}
			}else{ //first到mid之间元素无序,那么这时后半部分有序，尝试查找。
				//判断target是否在范围之内
				if (A[mid] < target && target <= A[last - 1]){
					first = mid + 1;
				}else{
					last = mid;
				}
			}
		}
		return -1;
	}
};

自我感觉这题优点难。