有人相爱，有人夜里看海，有人leetcode可以写一个礼拜。 呜呜呜是本人了

回顾一个十分简单的场景，猜数字游戏。我与友人A进行猜数字游戏，我心中想一个[0,100]的数字(假设我想一个10)，让A来猜，友人A先猜20，我说大了，那他之后会猜多少的值，肯定是[0,19]的数值，然后他说5，我说大了，接着会他会猜多少，是[6，19]的数，我和A默契还不错，她直接一个10，猜对了~

这个过程就是一个完美体现了二分思想，注意是思想。什么思想？在每一次查找之后都会将下一次查找范围缩小到一个区域。 这句话后面依旧会提到，要十分牢记。

二分法与场景不同的点在于，二分。二分法每一次查找都是对半分的，这是与上面场景不同的点，毕竟猜数字嘛，大家随意猜的。但是使用对半分可以减少盲目的查找，这也与随意不同的地方了。

了解了二分思想之后，直接上题目。

第一题:初步认识二分查找

leetcode704.二分查找

思路分析

我们着重于两个点：目标值，以及每一次查找的范围。题目就迎刃而解了 初次查找的时候，查找范围为数组首尾两个位置。我们定义两个指针在这两个地方，取其中间值，然后将这个中间值与target比较。进行的每一次比较我们都要缩小查找范围

• 如果中间值middle>target，那么查找的返回将缩小到middle的左边
• 如果中间值middle<target，那么查找的返回将缩小到middle的右边
• 如果中间值middle=target，那么就说明查找到了，返回即可

重复上面的操作，直到找到或者left到了right的右边(这就说明这个数组中没有相关值,返回-1) 注意点：缩小范围的时候我们说如果中间值middle>target，那么查找的返回将缩小到middle的左边，也就是指下一刻，right = middle - 1，为什么是middle-1而不是middle？此时我们判断的条件是middle>target，也就是说这个middle值比如不是目标值，所以可以放心跳过它，直接到[left,middle-1]的范围查找，排除了不必要的查找过程。 图解如下： 初始的时候：

第二次查找(以9为例子)： middle等于9，找到返回。

完整代码

int search(int* nums, int numsSize, int target){
    int middle = 0;
    int left = 0;
    int right = numsSize - 1;
    while(left <= right)
    {
        middle = left + (right - left) / 2;//防止溢出，leetcode这题可以写(right+left)/2的
        if(target > nums[middle])
        {
            left = middle + 1;
        }
        else if(target < nums[middle])
        {
            right = middle - 1;
        }
        else 
        {
            return middle;
        }
    }
    return -1;
}

第二题:理解边界值left

leetcode35.搜索插入位置

思路分析

看见logn和排序数组的字眼了嘛，直接就激起了我对二分的敏感了哈哈哈哈哈 这道与704类似，但是稍微难一点的地方在于寻找没有找到的时候，插入位置的确认，需要对left和right的指向有一定理解就很好做了！ 画图理解一下： 初始第一次查找：

第二次查找：

第三次查找： 此时left>right，我们的查找已经结束了。返回值就是left指向的位置。

注意前面说到，每一次查找都在缩小范围，这个范围指的是目标值的范围，那么第二幅图中，当left=right=middle的时候，此时的范围就是[left,right]，也就是说right右边都不是查找范围了，而此时是由于middle<target，所以才导致了left右移的。middle右边的值又都是比target大才导致right左移的，所以，middle的这个位置，是插入的前一个位置，那么left=middle+1就是答案了。

着重理解每一次left和right表示的意义。

完整代码

int searchInsert(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize - 1;
    int tmp = 0;
    while(left<=right){
        tmp = (left+right)/2;//也可以使用防止溢出的写法
        if(nums[tmp] > target){
            right = tmp - 1;
        }else if(nums[tmp] < target){
            left = tmp +1;
        }else{
            return tmp;
        }
    }
    return left;
}

第三题:理解边界值right

leetcode69.求Sqrt(X)

思路分析

我们使用第二题的思路来想，第二题中，我们的目标值如果在这个数组中就返回，如果不在，就返回数组中最后那个小于它的数后面的第一个位置。 而这题的目标值呢？这组整数中，如果存在恰好是平方根的整数就返回，如果不存在，就返回小于平方根的最近的第一个整数，其实就是返回上一个题中的right！

int mySqrt(int x){
    int left = 0;
    int right = x;
    while(left<=right){
        long long int middle = (left + right) / 2;//防止溢出的代码在这里就起作用了，这里使用防止溢出可以通过
        long long int m2 = middle * middle;
        if(m2 > x){
            right = middle - 1;
        }else if(m2 < x){
            left = middle + 1; 
        }else{
            return middle;
        } 
    }
    return right;
}

第四天:主动寻找边界

leetcode34.在排序数组中查找元素的第一个和最后一个位置

在看完前三题之后，如果说对于left和right的每一次取值的意义，以及对于二分思想：每一次都是在缩小范围有了理解之后，来道中等题吧！

思路分析

在前面我们一直没有提到的一个知识点，在这道题中展现出来了，但是呢这个点依旧是在说一个思想，每次查找必然是在缩小范围的。不过在写题的时候，一定会有相关疑问的-----对于偶数个数的数组，我们取middle的时候，可以取到两个值，但是前面我们都只取了前一个值，没有取后一个值，是不是所有题都可以只取前面的值呢？我们先带着疑问我们来写这题。 这题我们分隔成两个二分法来求解，第一个二分法来求左边界值，第二个二分法求右边界值。

求左边界： 在以往的写法中，当我们寻找到了middle = target的情况下，我们是直接返回的，但是现在不同了，因为target是多个的。我们要找的是个范围。当第一次找到middle的时候可以确定剩下存在的middle一定是在middle的左边或者就是middle的，所以将范围缩小到[left,middle]，到最后的left如果与target相等，那么就肯定是左边界了

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

求右边界： 如果是如下写法，那么说明踩坑了，这里就与上面我们说到的疑问相关了。

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

假设我们的数组为[1,1]，寻找右边界的时候，middle会一直等于left，陷入循环，寻找右边界，那么遇到相同值之后肯定是将值向右边靠近的，正确写法如下：

int right(int *nums, int numsSize, int target){
    int left = 0;
    int right = numsSize - 1;
    while(left < right){
        int middle = (left + right + 1) / 2;//这里要+1，表示值向右靠近
        if(target < nums[middle]){
            right = middle - 1;
        }else if(target > nums[middle]){
            left = middle + 1;
        }else{
            left = middle;
        }
    }
    int rightside = right;
    if(nums[rightside] == target) return rightside;
    else return -1;
 }

完整代码

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

 }
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    if(numsSize == 0) {
        *returnSize = 2;
        int *arr = (int*)malloc(sizeof(int)*2);
        arr[0] = -1;
        arr[1] = -1;
        return arr;
    }
    int l = left(nums, numsSize, target);
    int r = right(nums, numsSize, target);
    *returnSize = 2;
    int *arr = (int*)malloc(sizeof(int)*2);
    
    arr[0] = l;
    arr[1] = r;
    return arr;
}

最后

总的来说，二分法不是一个很难的知识点，理解好每一次查找的范围，我觉得这是十分有益于做题的。 代码不难，希望对大家有帮助，如果出现错误，及时指正我哟~祝大家学习愉快！！！