leetcode 33.搜索旋转排序数组 二分法

题目描述

leetcode 33.搜索旋转排序数组

---

思路

将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 $[l,mid]$ 和 $[mid+1,r]$ 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 $target$ 在不在这个部分：

• 如果 $[l,mid-1]$ 是有序数组，且 $target$ 的大小满足 $[nums[l],nums[mid])$，则我们应该将搜索范围缩小至 $[l,mid-1]$，否则在 $[mid+1,r]$ 中寻找。
• 如果 $[mid,r]$ 是有序数组，且 $target$ 的大小满足 $(nums[mid+1],nums[r]]$，则我们应该将搜索范围缩小至 $[mid+1,r]$，否则在 $[l,mid-1]$ 中寻找。

---

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();

        if(n==1)
            return (nums[0]==target)?0:-1;

        int l=0,r=n-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(nums[mid]==target) return mid;
            if(nums[0]<=nums[mid])//这里必须是<=，不然当数组长度为2时，是过不了的
            {
                if(nums[0]<=target&&target<nums[mid])
                    r=mid-1;
                else    
                    l=mid+1;
            }
            else
            {
                if(nums[mid]<target&&target<=nums[n-1])
                    l=mid+1;
                else
                    r=mid-1;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---