6-33.搜索旋转排序数组

题目描述：

解题思路：

• 自己刚拿到这道题目的时候，第一时间是想找到是在哪个位置上进行了旋转，然后再比较target的值。对于如何找到这个index值，若用暴力搜索法，时间已经超出了限制，更别提接下来的二分查找target了。
• 然后就想着二分查找，判断第mid和第mid+1的值的大小，如果num[mid] > num[mid+1]，说明index = mid + 1；否则我就思路混乱了。
• 接着看了官方解析：
  这个有序数组，若以mid为分界，一定是一半有序，一半无序。因此就比较nums[0]和nums[mid]的值，就能判断出哪半边是无序的。
  如果[0,mid]有序，判断target是在此有序中还是在另外一边的无序中。
  否则[mid,right]有序，再次判断target在哪半边
• 通过这种分成两半进行判断在哪边的过程，就能剔除掉如果 target < nums[mid]，结果你就去<mid的地方找，忽略了target可能在>mid的地方。

代码：

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        if(len == 0){
            return -1;
        }
        if(len == 1){
            return target == nums[0] ? 0 : -1;
        }
        int left = 0;
        int right = len - 1;
        while (left <= right){
            int mid = (left + right) / 2;
            if (target == nums[mid]){
                return mid;
            }
            if (nums[0] <= nums[mid]){//[left,mid]有序  这个=号要考虑left=right的情况
                if(nums[left] <= target && nums[mid] > target){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{//[mid,right]有序
                if(nums[mid] < target && nums[right] >= target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

6-33.搜索旋转排序数组

原文：https://www.cnblogs.com/forrestyu/p/14672370.html