目录

一、前言

 二、二分思想

✨算法引出 

✨算法形成的条件

 三、二分查找详解

✨写法1：左闭右闭 

 🥝正确的写法（正确演示）

 🍍错误的写法  (错误演示)

✨写法2：左闭右开

🍎正确的写法（正确演示）

🍐错误的写法  (错误演示)​​​

✨ 总结

四、常考面试题

💦搜索插入位置

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

💦x的平方根

💦有效的完全平方数

五、共勉

---

一、前言

        二分法的思想十分容易理解，但是二分法 - 边界 - 处理问题大多数人都是记忆模板，忘记模板后处理边界就一团乱（👁:“我懂了”， ✋ :"你懂个🔨"​）因为我此前也是记忆模板，所以现在想通过一边学习，一边将所学记录成博客进行复习（费曼学习法），希望以后能自己推导出边界如何处理，而不仅仅是记忆模板。欢迎一起交流学习，如有看法不一样之处也欢迎留言一起讨论！

        所以本博客我主要解释了二分法的左闭右闭区间，左闭右开区间两种写法，并且每个写法都举了相应的反例，范围写错的话可能会出现的错误等…

 二、二分思想

✨算法引出 

故事分享🏬： 

        有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此，图书馆丢了 N - 1 本书。

保安怎么知道只有一本书📖没有登记出借，万一全部都没有登记呢​？ 

 ✨算法形成的条件

这个故事其实说出了二分查找需要的条件 ！！!

用于查找的内容逻辑上来说是需要有序的查找的数量只能是一个，而不是多个

 比如在一个 有序的数组 并且 无重复元素 的数组中，例如[1, 2, 3, 4, 5, 6]，需要查找3的位置就可以使用二分查找。

        因为查找的区间是不断迭代的，所以确定查找的范围十分重要，主要就是左右区间的开和闭的问题，开闭不一样，对应的迭代方式也不一样，有以下两种方式：

左闭右闭: <code>[left, right]

左闭右开: [left, right)

 三、二分查找详解

首先我们通过一道题，来深入了解 二分查找 的细节

题目：二分查找

链接：704. 二分查找 - 力扣（LeetCode）

题目分析：

 二分法的思想很简单，因为整个数组是有序的，数组默认是递增的。

首先选择数组中间的数字和需要查找的目标值比较如果相等最好，就可以直接返回答案了如果不相等

           1. 如果中间的数字大于目标值，则中间数字向右的所有数字都大于目标值，全部排除

           2. 如果中间的数字小于目标值，则中间数字向左的所有数字都小于目标值，全部排除

 二分法就是按照这种方式进行快速排除查找的

 tips:

不用去纠结数组的长度是奇数或者偶数的时候，怎么取长度的一半，以下说明，可以跳过。

⚡当数组的长度为奇数的时候⚡

 是奇数的情况很简单，指向中间的数字很容易理解，如果需要查找的数字为29

因为29大于中间的数字大于11，所以左边的所有数字全部排除 

⚡ 当数组的长度为偶数的时候⚡

        这个时候 中间的数字 和 两边的数字 数量就不一样了（刚开始学习二分法的时候我经常纠结这个问题，和另外一个 长度除2得到的是最中间的数吗的问题，我相信不止我一个人纠结过……但其实这是同一个问题，每次长度除2，如果长度为奇数，得到的中间的数字两边数字数量相同，如果长度为偶数就为上图中间的数字两边的相差为 1）

但是千万不要一直纠结中间的数字两边的数字数量不一样这个问题，因为： 

两边数量不一样是一定会出现的情况但是这种情况并不影响我们对中间数字和目标数字大小关系的判断

只要中间数字大于目标数字，就排除右边的只要中间数字小于目标数字，就排除左边的

所以数组长度是偶数还是奇数这个真的不重要，不影响怎么排除的问题，无非是多排除一个数字或者少排除一个数字 

真正影响的是中间那个数字到底该不该加入下一次的查找中，也就是边界问题

✨写法1：左闭右闭 

 二分法最重要的两个点：

while循环中 left 和 right 的关系，到底是 left <= right 还是 left < right迭代过程中 middle 和 right 的关系，到底是 right = middle - 1 还是 right = middle

 🥝正确的写法（正确演示）

 第一种写法：每次查找的区间在 <code>[left, right]（左闭右闭区间），根据查找区间的定义（左闭右闭区间），就决定了后续的代码应该怎么写才能对。因为定义 target 在[left, right]区间，所以有如下两点：

循环条件要使用 while(left <= right)，因为当 (left == right) 这种情况发生的时候，得到的结果是有意义的if(nums[middle] > target) ， right 要赋值为 middle - 1， 因为当前的 nums[middle] 一定不是 target ，需要把这个 middle 位置上面的数字丢弃，那么接下来需要查找范围就是 [left, middle - 1]

 代码如下：

class Solution {

public:

int search(vector<int>& nums, int target)

{

int left = 0; //下标从0开始

int right = nums.size() - 1; //定义target在左闭右闭的区间里[left,right] nums.size()求数组中元素个数

while (left <= right) //当left == right时，区间[left, right]仍然有效

{

int mid = left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2；int会向下取整

if (nums[mid] > target)

{

right = mid - 1; // target 在左区间，所以[left, middle - 1]

}

else if (nums[mid] < target) // target 在右区间，所以[middle + 1, right]

{

left = mid + 1;

}

else // nums[middle] == target

{

return mid; // 数组中找到目标值，直接返回下标

}

}

return -1; //未找到目标值

}

};

 图例解析：

 首先看一个数组，需要对这个数组进行操作。需要对33进行查找的操作，那么target 的值就是33

首先，对 left 的值和 right 的值进行初始化，然后计算 middle 的值

<code>left = 0, right = size - 1middle = (left + (right - left) / 2 )

比较 nums[middle] 的值和 target 的值大小关系

<code>if (nums[middle] > target)，代表middle向右所有的数字大于targetif (nums[middle] < target)，代表middle向左所有的数字小于target既不大于也不小于就是找到了相等的值

nums[middle] = 13 < target = 33，left = middle + 1

 见下图：

循环条件为 <code>while (left <= right)

此时，left = 6 <= right = 11，则继续进行循环

当前，middle = left + ((right - left) / 2)，计算出 middle 的值

 计算出 middle 的值后，比较 nums[middle] 和 target 的值，发现：

nums[middle] = 33 == target = 33，找到目标

 🍍错误的写法(错误演示)

 对应第一种正向的写法，我们把循环条件修改看看会发生什么事

原查找区间 [left, right]原循环条件是 while (left <= right)

修改后题目对应的条件： 

查找区间不变，仍然是[left, right]查找数字为27 (target = 27)循环条件修改为while (left < right)

 代码如下：

<code>class Solution {

public:

int search(vector<int>& nums, int target)

{

int left = 0; //下标从0开始

int right = nums.size() - 1; //定义target在左闭右闭的区间里[left,right] nums.size()求数组中元素个数

// 错误写法

while (left < right) //当left == right时，区间[left, right]仍然有效

{

int mid = left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2；int会向下取整

if (nums[mid] > target)

{

right = mid - 1; // target 在左区间，所以[left, middle - 1]

}

else if (nums[mid] < target) // target 在右区间，所以[middle + 1, right]

{

left = mid + 1;

}

else // nums[middle] == target

{

return mid; // 数组中找到目标值，直接返回下标

}

}

return -1; //未找到目标值

}

};

 好了，现在开始用图片模拟过程

初始化一个数组，计算 middle 的值

根据计算的 middle 值确定 nums[middle]

因为nums[middle] = 13 < target = 27，所以left = middle + 1

继续计算 middle 的值

因为 nums[middle] = 33 > target = 27，所以 right = middle - 1

接着计算 middle 的值

因为 nums[middle] = 22 < target = 27，此时 left = middle + 1，此时 left = right，而循环条件为while (left < right)，所以还未找到27 的情况下算法就跳出了循环，返回 -1

 ✨写法2：左闭右开

🍎正确的写法（正确演示）

第二种写法：每次查找的区间在 [left, right)，（左闭右开区间）， 根据区间的定义，条件控制应该如下：

循环条件使用 while (left < right)if (nums[middle] > target)， right = middle，因为当前的 nums[middle] 是大于 target 的，不符合条件,不能取到 middle，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 middle。

代码如下： 

<code>class Solution {

public:

int search(vector<int>& nums, int target)

{

int left = 0;

int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)

while (left < right) // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <

{

int mid = left + ((right - left) >> 1); // >>右移运算符 向右移动一位相当于除2

if (nums[mid] > target)

{

right = mid; // target 在左区间，在[left, middle)中

}

else if (nums[mid] < target)

{

left = mid + 1; // target 在右区间，在[middle + 1, right)中

}

else // nums[middle] == target

{

return mid; // 数组中找到目标值，直接返回下标

}

}

return -1; // 未找到目标值

}

};

图列解析如下：

第一步是初始化 left 和 right 的值，然后计算 middle 的值 

left = 0, right = size循环条件while (left < right)

 因为是左闭右开区间，所以数组定义如下：

计算 middle 的值

比较 nums[middle] 和 target 的大小：因为 nums[middle] = 22 > target = 3所以 right = middle

符合循环的条件，接着计算 middle 的值

比较 nums[middle] 和 target 的大小：因为 nums[middle] = 9 > target = 3所以 right = middle

符合循环的条件，继续计算 middle 的值

比较 nums[middle] 和 target 的大小关系：因为nums[middle] = 0 < target = 3所以 left = middle + 1

符合循环条件，接着计算 middle 的值

比较 nums[middle] 和 target 的关系：nums[middle] = 3 == target = 3成功找到 target

🍐错误的写法(错误演示)

​​​​​​​​​​

对应第二种正确的写法，照样把循环条件修改，看会发生什么事

正确的写法中条件为： 

查找原区间 [left, right)循环条件为 while (left < right)

 修改后题目对应的条件：

查找区间不变，仍然是 [left, right)

循环条件修改为：while (left <= right)

查找的数字为26（数组中不存在这个数字！！！）

代码： 

<code>class Solution {

public:

int search(vector<int>& nums, int target)

{

int left = 0;

int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)

// 错误的写法

while (left <= right) // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <

{

int mid = left + ((right - left) >> 1); // >>右移运算符 向右移动一位相当于除2

if (nums[mid] > target)

{

right = mid; // target 在左区间，在[left, middle)中

}

else if (nums[mid] < target)

{

left = mid + 1; // target 在右区间，在[middle + 1, right)中

}

else // nums[middle] == target

{

return mid; // 数组中找到目标值，直接返回下标

}

}

return -1; // 未找到目标值

}

};

 图例详解：以下是演示全过程：

同样，开始初始化一个数组

先计算 middle 的值

判断 nums[middle] 和 target 的大小关系：nums[middle] = 22 < target = 26

left = middle + 1 （其实这里nums[left] 已经等于27，26不可能找到，接下去就看算法是否能够知道数组中不存在26并且返回-1 了）

符合循环条件，计算 middle 的值

判断 nums[middle] 和 target 的大小关系：nums[middle] = 57 > target = 26right = middle

满足循环条件，接着计算 middle 的值

比较 nums[middle] 和 target 的大小关系：nums[middle] = 33 > target = 26right = middle

符合循环条件，继续计算 middle 的值

比较 nums[middle] 和 target 大小关系，因为 nums[middle] = 27 > target = 26，所以 right = middle，自此，left 和 right 相遇，但是循环条件被我们修改成 while (left <= right) 会接着做循环

接下来就是死循环因为 middle = left + ((right - left) / 2)，当 left = right 的时候，middle 的值不会继续改变middle 不继续改变，由于right = middle，right 也不会改变，所以三个数字自此开始不会继续改变循环条件 while (left <= right) 却仍然满足，不会跳出循环死循环……

✨ 总结

二分法最重要的两个点，就是循环条件和后续的区间赋值问题

 因为两者是相互联系，相互影响的，所以就需要两者统一，如果两者不统一，就会出现问题

所以循环条件和赋值问题必须统一，也就是循环不变量。

见到数组的题，我们可以先看一下，有没有顺序，如果有，可以根据题意考虑可以合不合适使用二分查找。

然后再写二分查找时，如何保证你写的二分查找是正确的，可以多想一下这段话

要对区间定义想情楚，区间的定义就是不变量，这里建议可以多画画图.

要在二分查找过程中，保持不变量，就是要用while寻找每一次边界的处理，都要坚持根据区间的定义来操作，这就是循环不变量的规则。

写二分法，区间定义要想清楚，

一般有两种，左闭右闭 [ left , right ]       左闭右开  [ left , right )

四、常考面试题

 💦搜索插入位置

 链接：35. 搜索插入位置

<code>class Solution {

public:

int searchInsert(vector<int>& nums, int target)

{

// 双指针

int left = 0,right = nums.size();

int mid = 0;

// 左闭右开

while(left<right)

{

mid = left+((right-left)>>1);

if(nums[mid]>target)

{

right = mid;

}

else if(nums[mid]<target)

{

left = mid+1;

}

else{

return mid;

}

}

return left;

}

};

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

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

<code>class Solution {

public:

// 二分查找

int binarysearch(vector<int>& nums, float target)

{

int left = 0;

int right = nums.size();

while(left<right)

{

int mid = left+(right-left)/2;

if(nums[mid]>target)

{

right = mid;

}

else if(nums[mid]<target)

{

left = mid+1;

}

// 这里不能等于 mid

}

// 返回 小于最近整数的前一个位置

return left;

}

vector<int> searchRange(vector<int>& nums, int target)

{

vector<int> v(2,-1);

// 两次二分

int strat = binarysearch(nums,target-0.5);

int end = binarysearch(nums,target+0.5);

// 没找到

if(strat==end)

{

return v;

}

else

{

v[0] = strat;

v[1] = end-1;

}

return v;

}

};

 💦x的平方根

 链接：69. x 的平方根 

<code>class Solution {

public:

int mySqrt(int x)

{

// 1 和 0 的算数平方根为自身

if(x<=1)

{

return x;

}

// 左闭右开 [1,x/2+1)

// 所有大于等于4的数，其算数平方根小于等于它的一半

int left = 1;

int right = x/2+1;

while(left<right)

{

int mid = left+((right-left)>>1);

if((long)mid*mid<x)

{

left = mid+1;

}

else if((long)mid*mid>x)

{

right = mid;

}

else

{

return mid;

}

}

return left-1;

}

};

💦有效的完全平方数

链接：367. 有效的完全平方数

<code>class Solution {

public:

bool isPerfectSquare(int num)

{

if(num<=1)

{

return true;

}

int left = 1;

int right = num/2+1;

while(left<right)

{

int mid = left+((right-left)>>1);

if((long)mid*mid < num)

{

left = mid+1;

}

else if((long)mid*mid > num)

{

right = mid;

}

else

{

return true;

}

}

return false;

}

};

五、共勉

 以下就是我对 二分查找 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对【C/C++】的理解，请持续关注我哦！！！！！