leetcode 33 搜索旋转排序数组

题目原地址

这个题需要仔细思考一下判断的条件，由于不是完全有序而是部分有序，所以不能像普通二分一样简单的判断大小

举个简单的例子
对于数组**nums=[6,7,8,9,1,2,3,4]**来说

left=0,right=8

通过二分计算出的中点idx=4 ,值为1 ，如果中点就是target，这当然皆大欢喜，直接返回对应的坐标就好

如果不是，这时候中点将数组划分成了两部分，其中至少有一部分是有序的数组，在本例中，中点右侧的**[2,3,4]**有序

那该如何判断哪边的数组有序呢，也比较简单，只需要比较nums[mid]与nums[left]的大小即可，若 nums[mid]>nums[left]nums[mid]>nums[left],则mid左侧有序，否则右侧有序。

之后我们需要比较target与num[mid]的大小，这时候也会涉及到分类讨论，由于markdown这传图片麻烦得很，就不再赘述了，自己画画图就能方便的看出，也可以看我发的连接里的官方题解里的视频讲解，那里面有图方便理解

代码如下

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
class Solution {
public:
    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;

        int l=0,r=n-1;
        while(l<=r){
            int mid = (r-l)/2+l;
            if(nums[mid]==target) return mid;
            if(nums[mid]>=nums[l]){
                if(nums[mid]<target){
                    l=mid+1;
                }else{
                    if(target<nums[l]) l=mid+1;
                    else r=mid-1;
                }
            }else{
                if(nums[mid]>target){
                    r=mid-1;
                }else{
                    if(target<nums[l]) l=mid+1;
                    else r=mid-1; 
                }
            }
        }
        return -1;
    }
};