33. 搜索旋转排序数组

题目描述

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

( 例如，数组 [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

示例2：

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

思路

1.从本题的时间复杂度来看，肯定是要使用二分搜索类似的算法。
2.既然是二分搜索，每次就需要决定下次搜索的方向，我们可以将所有的搜索方向都列出来，方便我们分析合并。

1.二分后，左边的数组是升序的(nums[0]<nums[mid])
1.1 target>nums[mid]：应该往右边搜索
1.2 target<nums[mid]并且target<nums[0]：应该往右边搜索
1.3 target<nums[mid]并且target>=nums[0]：应该往左边搜索

2.二分后，左边的数组是存在翻转点的(nums[0]>nums[mid])
2.1 target<nums[mid]并且target>=nums[0]：应该往左边搜索
2.2 target<nums[mid]并且target<nums[0]：应该往左边搜索
2.3 target>nums[mid]并且target<nums[0]：应该往右边搜索
2.4 target>nums[mid]并且target>=nums[0]：应该往左边搜索

1. 按照二分搜索模板，编写代码即可。

Java代码实现

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (left+right)/2;
            if(nums[mid] == target)
                return mid;
            else{
                //左边这一半元素并非单纯的降序
                if(nums[0]>nums[mid]){
                    //如果target比第一个元素大，说明target有可能在左边，因为右边的元素没有比nums[0]更大的了
                    if(target>=nums[0] || (target<=nums[0] && target<nums[mid]) ){
                        right = mid - 1;
                    }else{
                        left = mid + 1;
                    }
                }
                //左边这一般元素是单纯的升序
                else{
                    //如果target>mid  或者 target<mid并且target<nums[0] target都可能在右边
                    if(target>nums[mid] || (target<nums[mid] && target<nums[0])){
                        left = mid + 1;
                    }else {
                        right = mid - 1;
                    }
                }
            }
        }
        return -1;
    }