这里推荐一个很方便记忆和使用的二分查找模板希望对大家有用。二分查找Binary Search是一种高效的有序数组查找算法通过每次将搜索范围缩小一半来快速定位目标值。其时间复杂度为 O(log n)适用于静态数据或频繁查询的场景。比如一个序列1 2 4 5 5 5 5 6 6 7 9 10现在我们查找 5 这个数字。该序列中有 4 个 5分别查找第一个 5 和最后一个 5 的位置。一、查找右边序列的左端点我们现在先来查找第一个5的位置。二分查找利用的是二段性所以我们把上面的序列根据要找的值来进行分段。二分查找最后会找到分段的地方所以我们分段时要将需要找的第一个5的位置定在分段的交界处。// 假设上面的序列是放在 vector 中的对象名称为 vintleft0,rightv.size()-1;while(leftright){intmidle(ri-le)/2;if(v[mid]5)leftmid1;elserightmid;}循环条件while(left right)必须是 left right不能有等于因为循环到最后就会两个相等相等的那个就是结果所以为了不形成死循环循环条件不能有等号。left 和 right 的移动left mid 1;right mid;一般我们会想到leftmid1;rightmid-1;但这里并没有查验 mid 指向的位置的值是否为目标值所以我们并不能直接否认 mid 的位置将序列范围压缩到 [mid 1, right] 或 [left, mid -1]。事实上在该情况下left 可以更新为 mid 1 right 却不能更新为 mid -1我们要求的是右序列的左端点当 mid 指向的值位于左边序列时需要移动 left 到 mid 位置或 mid 1 位置考虑到查找的一定不会位于 mid 的位置比如上面的例子查找的是 5而左边的序列都是小于 5 的当 mid 位于左边的序列时一定不会有 5所以跳出这个序列即可所以 left mid 1 即可。但当 mid 指向的值位于右边序列时需要移动 right 到 mid 或 mid-1 的位置此时只能选择 mid 的位置因为查找可能位于 mid 的位置因为右边都是 5 的mid 可能正好位于我们所查找的位置一旦 right mid -1 那就会错过 mid 这个位置的正确下标了。中间下标的计算mid le (ri - le)/2;原本的形式为intmid(leftright)/2;但这样计算有一个缺点如果 left 和 right 的和超过类型的范围那计算就会出错。所以采用上面的写法。计算中间值有两种写法intmid(leftright)/2;// 对应的不超范围的写法为mid left (right-left)/2;intmid(leftright1)/2;// 对应的不超范围的写法为mid left (right-left1)/2;这两种写法的区别是当序列个数为偶数时第一个mid会指向数组最中间两个的左边而第二个会指向右边的那个。求左端点只能使用第一种写法否则会造成死循环。二、查找左边序列的右端点现在来查找最后一个5的位置。依据将要查找的位置定于分段处来进行分段。二分查找最后会找到分段的地方所以我们分段时要将需要找的最后一个 5 的位置定在分段的交界处。// 假设上面的序列是放在 vector 中的对象名称为 vintleft0,rightv.size()-1;while(leftright){intmidle(ri-le1)/2;if(v[mid]5)leftmid;elserightmid-1;}道理类似左端点的查找这里不多赘述。三、关于分段一个查询值时的分段1 2 4 5 6 7 8 9 10比如在上面的序列中我们想要查询 8 这个值有两种分段方式两种方式都可以区别只是求左端点还是右端点。此时延伸一下即如果有多个目标值不同的分段就会导致得到不同的下标如下图。没有查询值时的分段上面看到了序列中有所要查询的值下面看一下如果没有查询值时的情况。1 2 4 5 5 5 5 6 6 7 9 10对于上面的序列如果要查询 8 这个值肯定是查不到的但可以查到离他最近的最近的就是 7 和 9 的位置。我们分段时是按 8 来进行分段的所以如果要查到 7 的位置就是要查找左端点如果要查找 9 的位置就是要查找右端点所以根据需要来写代码即可。但要注意一点对于分段时等于的处理。如果序列中确实没有要查找的值那等于的情况分到那边都可以但如果不清楚要查找的值到底在序列中有没有那就要注意等号分到哪边了会有不同的结果。四、关于未在序列中的数的查找1 2 4 5 5 5 5 6 6 7 9 10如果这个序列要查找 0那很明显在该序列范围外每次计算的 mid 总是会落在右区间所以一定会是 right 移动而 left 不动最后会移动到 left 和 right 相等然后退出循环如下图。如果查找的是超过序列最大值的同理是 right 不动而 left 总向右移动最终 left 和 right 相等然后退出循环如下图。