题目描述

Suppose an array sorted in ascending order 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.

Your algorithm’s runtime complexity must be in the order of O(log n).

题意：一个有序数组，将数组后面一部分元素挪到数组最开始的地方。在这个移动后的数组中找到某个数是否存在，返回其下标。$O(logn)$时间复杂度

样例

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

算法1

题解1：（使用两次二分搜索）数组也有可能还是依次有序的（从后面移了0个元素），那么直接进行二分即可。如果移动后的数组不是递增的话，那么这个数组由两个递增的子数组组成，如上题中的$[4,5,6,7] and[0,1,2]$。如果我们可以判断这两个数组的分界点，同时判断出target在哪个子数组中，再使用一次二分就可以解决问题了。

• 很明显，如果一个元素小于前一个元素，那么这个元素是第二个子数组的开始。如何使用二分查找这个边界呢？因为这个边界肯定存在（不然就是完全升序了，二分查找模板一），那么问题就在于如何进行边界转移了，可以发现第一个数组中的元素都大于$nums[0]$,第二个数组中的元素都小于$nums[0]$，如果$nums[mid] \geq nums[0]$，说明当前$mid$在第一个数组中说明$mid$偏小；否则$mid$在第二个数组中，$mid$偏大。
• 其次，如果$target\geq nums[0]$，那么目标可能在第一个数组中；否则可能存在于第二个数组中。

C++ 代码

    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n == 0) return -1;
        if(n == 1) return (nums[0] == target)? 0 : -1;//0-1特判
        int firstLessIndex = -1;//标记第二个数组的第一个元素下标
        int left = 1,right = n - 1;//二分匹配模板一
        while(left <= right)
        {
            int mid = (left + right) / 2 ;
            if(nums[mid] < nums[mid - 1]) 
            {
                firstLessIndex = mid;
                break;
            }
            else if(nums[mid] > nums[0])
                left = mid + 1;
            else
                right = mid - 1;
        }
        if(firstLessIndex == -1)//说明没有找到大于前一个元素的元素，数组是升序的
            left = 0,right = n - 1;
        else if(target >= nums[0])//目标在第一个数组中
            left = 0,right = firstLessIndex - 1;
        else//目标在第二个数组中
            left = firstLessIndex ,right = n - 1;
        while(left <= right)//二分查找模板一
        {
            int mid = (left + right)  / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

算法2

题解2:（使用一次二分搜索）从题解1我们可以知道$nums[0],nums[mid],target$三者的大小关系决定了边界的转移。我们能否使用更巧妙的形式来进行二分搜索呢？其实每一个$nums[mid]$和两个数组的边界把整个数组划分为了三个部分。如果$mid$落在第一个数组中，则是将第一个数组分成了两个部分；否则将第二个数组分为了两部分。

C++ 代码

    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return -1;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= nums[0]) { // nums[mid]在数组前半部分。
               // target在第一个数组的第二个部分，但是我们不知道具体的分界下标，没办法移动r,下面同理                              //target只可能在[mid+1, r]中。
                if (target > nums[mid])
                    left = mid + 1;
                else if (target < nums[0])
               // target在第二个数组中，但是我们这个时候不知道具体的分界下标
               //target只可能在[mid+1, r]中。
                    left = mid + 1;
                else if (target <= nums[mid] && target >= nums[0])
               //   在第一个数组的第一部分
                    right = mid;
            }
            else { // nums[mid]在数组后半部分
                // 在第一个数组中，但是这个时候我们不知道具体的分界下标，target只可能在[l, mid]中
                if (target >= nums[0])
                    right = mid;    
               //在第二个数组的第一部分，但是这个时候我们不知道具体的分界下标
               //target只可能在[l, mid]中
                else if (target <= nums[mid])
                    right = mid;
               //在第二个数组的第二部分
                else if (target > nums[mid] && target < nums[0])
                    left = mid + 1;
            }
        }
        return nums[left] == target ? left : -1;
    }

算法2

    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return -1;
        int left = 0, right = n - 1;
        while(left <= right)//使用二分查找模板二
        {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] >= nums[0])//如果mid在第一个数组中
            {
                if(target > nums[mid]) left = mid + 1;
                else if(target >= nums[0]) right = mid - 1;
                else left = mid + 1;
            }else{//如果mid在第二个数组中。
                if(target < nums[mid]) right = mid - 1;
                else if(target >= nums[0]) right = mid - 1;
                else left = mid + 1;
            }
        }
        return -1;
    }

• 我之前写的 二分边界详细总结不能很好的处理这一题的题解二的情况（感谢@TK）。其实二分查找的边界转换就是不断的排除不可能是解的搜索空间，只要弄清楚在不同的条件下，哪些是潜在的可行解，哪些不是可行解。弄清楚三种最普遍的二分模板，其他情况也可以举一反三，迎刃而解。