刷代码随想录有感（3）：二分查找

额，这次没啥问题，主要是写一下加深记忆。

题目很简单，二分查找，题目如下：

以下是代码（我用的是左闭右闭模板）：

int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){//left能与right取等说明是左闭右闭模板
            int mid = (left + right) / 2;
            if(nums[mid] > target) right = mid - 1;
            else if(nums[mid] < target) left = mid + 1;
            else return mid;
        }
 
        return -1;

思路解析：Carl说了两种写法，分别是左闭右闭与左闭右开区间。二分查找最容易弄混的就是边界问题，对于我这种啥都不懂的初学者来说还是先记住模板吧。

        （1）：[left, right]形式，定义left为0，right为nums.size() - 1.

                     好，第一个问题，为什么right取size - 1 ？因为右边是闭的被包含的，需要取到右边界的下标，也即size - 1.

                     继续，while(left<=right)，为什么是<=号而不是<号？拿[1,1]举例，那必然是可以左右相等的，左边可以取到1，右边也可以取到1，那为什么不能相等呢，你说对不对？

                     再来，在while循环里面定义int mid = (left + right) / 2; 为什么要在while循环里面定义mid？原因是mid是在被不断更新的，你想让它被一直更新就要放在while循环里面。

                     接着，if(nums[mid] > target)说明target在左半边，所以需要缩右边界，right = mid - 1

                     为什么要-1 ？因为是[left, right]形式，右边是闭的，如果right = mid则代表包含mid值，可是先前的nums[mid]已经使用过了mid,再用就冲突了，所以不能包含进来，而数组元素又是连续的以整数下标储存的，故而-1.

                     接着，else if(nums[mid] < target)说明target在右半边，所以需要缩左边界，left = mid + 1 ,理由与缩右边界一致：因为left是闭所以会再次包含mid，为了不冲突所以将mid + 1.

                     最后，else表示相等情况，所到最后了，直接return mid就是答案。

                     在while循环外return -1代表从上面代码执行到最后都没找到。

         （2）：[left, right)形式，定义left为0，right为nums.size().

                      

//左闭右开模板
int left = 0;
int right = nums.size();//右开取不到边界，可以放心等于
 
while(left < right)
{
    int mid = (left + right) / 2;
    
    if(nums[mid] > target) right = mid;
    else if(nums[mid] < target) left = mid + 1;//左边界仍然闭，所以不能取到
    else return mid;
}
 
return -1;

                     为什么right不 -1 了？观察到右边界是开的就算等于也没事，反正取不到。

                     while(left < right)，继续拿[1, 1)举例，左边能取到1而右边不行，如果取=则会冲突，所以不行。

                     if(nums[mid] > target)不变，但需要更改缩的右边界，right = mid没有1，因为取了也包含不到mid，而左边界仍然需要+1因为左边界还是闭的，如果不加1还是能在下一轮取到与第一轮冲突。

综上所述，两模板最大的不同在于①right的初值②right的更新值

企业里常用的就这俩种方法，暂且到此为止。