当二分查找遇到旋转数组

leetcode上有这么一道旋转数组的题目。地址

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。
-------------------------------------------------
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
（就是查元素0，在不在数组中，如果在返回下标值，如果不在返回-1）


示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

题目中强调时间复杂度必须是O(logn)，首先想到的是二分查找。

普通的有序数组，二分查找很容易，先瞄一眼

先上伪代码哈
public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
        	int mid = (right - left)/2 + left;
        	if(nums[mid] == target){
        		return mid;
        	}
        	if(nums[left] < target){
        		left = mid;
        	} else{
        		right = mid;
        	}
        }
        return -1;

二分查找，通过比较mid与target的值，就可以确认移动边界了。但现在对于旋转数组，比较一次，没法确认移动哪个边界。

题目又明确要求，时间复杂度是O(log n)。那就得好好想想，怎样才能移动边界的问题。

题目已知条件，原数组是递增的。旋转之后，后一段的小于前一段的任何一个。
这里分析下，target位于第一段的情况（即target > nums[0]），另一种情况，与之类似。

中间值 mid = (left + right)/2

如果 nums[left] < nums[mid] < target -- (图中区间1的位置)
那么不用想，左边界往右移，即 将mid赋值给left。

若nums[mid]落在区间2和区间3，右边界左移。思路就是这样，上代码。

加强版的二分查找搞起！！！！

------------------------------------------------------------

    public int search(int[] nums, int target) {
        if(null == nums || nums.length == 0) return -1;
        int len = nums.length;
        int left = 0;
        int right = len -1;
        while(left <= right){
            int mid = (right - left)/2 +left; // 取中间值
            if(nums[mid] == target){
                return mid;
            }
            if(nums[left] <= target){
                if(nums[mid] < nums[left] || nums[mid] > target){ // 落在2或3区间
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }                
            }else{
                 if(nums[mid] > nums[right] || nums[mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                } 
            }            
        }
        return -1;
    }