【手绘漫画】图解LeetCode之搜索旋转排序数组（LeetCode33题），二分查找

！

正文共：1375字 22图

阅读大概需要：4分钟

跟随小博主，每天进步一丢丢

1、前言

手绘漫画系列正式上线！！！"图解LeetCode刷题计划" 来了！！！

今天是第六期，争取每天一期，最多两天一期，欢迎大家监督我。。。

目前的题目暂定LeetCode

一两个月必定开启剑指offer，敬请期待。

今日依旧还是是二分查找算法~

2、题目

首先看一下题目，

排序，旋转，不重复，没错，就是我，【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值（LeetCode153题）大声喊到。

嘻嘻，不同之处是什么呢？就是153是最小值，而33则是目标值，当然题目的长度也是不一样的~

3、正文

首先分析一下情况，

寻找的目标是 target，在这里是1，

开始二分法，

如何判断一个区间是不是递增或递减的，因为数组是排序的，所以只要比较两端点，如果左端点小于右端点，那么数组递增。

如果目标在两端点之间，那么就执行 left=mid+1。

记得先判断，nums[mid] 和 target 是不是相等。

复杂度：

• 时间复杂度：和二分搜索一样，是 。
• 空间复杂度：。

4、代码

int search(int* nums, int numsSize, int target){
    int left=0;int right=numsSize-1;
    int mid=left+(right-left)/2;
    while(left<=right){
        if(nums[mid]==target){
            return mid;
        }
        if(nums[left]<=nums[mid]){
            if(nums[mid]>=target&&target>=nums[left]){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
        else if(nums[left]>nums[mid]){
            if(nums[mid]<=target&&target<=nums[right]){
                left=mid+1;
            }
            else{
                right=mid-1;
            }
        }
        mid=left+(right-left)/2;
    }
    return -1;
}

5、讨论

最近在认真研究一个问题，当然不是谈婚论嫁，而是二分查找，二分查找算法的难度不大，但是细节多到爆炸，，，

• 比如 为什么 while 循环的条件中是 <=，而不是 < ？；
• 再比如 为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid；
• 或者 为啥好多的 mid = left + (right - left) / 2; 而不是 mid = (right + left) / 2;

准备下期出个分析，看看能不能讲明白了。。。