关键词：

看到一个大佬的博客详解二分查找算法，有一段内容让我深有感触：

我周围的人几乎都认为二分查找很简单，但事实真的如此吗？二分查找真的很简单吗？并不简单。看看 Knuth 大佬（发明 KMP 算法的那位）怎么说的：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...

这句话可以这样理解：思路很简单，细节是魔鬼。

这两个月刷题遇到不少要用到二分查找的题。当年学数据结构的时候觉得这是一个相当直观且好理解的算法，但是真正刷题时觉得这个算法需要注意的坑还是挺多的。最普通的应用就是找某个元素的索引（数组有序且不重复），再复杂一些的还有找某个元素最左边或最右边的索引。更高端的有对数组的索引或者数组中整数的取值范围进行二分查找，不过这一块还是万变不离其宗，查找的范围依旧是[left, right]，难点在于要怎么找到二分查找的对象。

二分查找基本框架

def binarySearch(arr: List[int], target: int):
    n = len(arr)
    left, right = 0, ...  # 左右边界的赋值可变
    while left ... right:  # 需要注意有没有等号
        mid = left + (right - left) // 2
        if arr[mid] == target:
            ...  # 要不要直接return
        elif arr[mid] < target:
            left = ...  # 要不要加一
        elif arr[mid] > target:
            right = ...  # 要不要减一
    return ...  # 有返回mid的，有left的各种

上面一段代码中的...部分是需要根据题目需要修改的地方，也就是二分查找的细节所在。另外，计算mid的公式也可以写成mid = (left + right) // 2，按上面那样写是为了防止溢出（虽然在Python里并不会有整型溢出的问题，不过最好养成这个习惯）。

找一个数的索引

这是二分查找最简单的一种应用，只要学习过数据结构肯定闭着眼睛都能写出来。

def binarySearch(arr: List[int], target: int):
    n = len(arr)
    left, right = 0, n - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid - 1
    return -1  # 没有找到，返回 -1

这里有几个地方需要注意。

左右指针的赋值

左右指针的初始化决定了搜索区间是开区间还是闭区间

左右指针初始化为left, right = 0, n - 1，也就是说搜索区间是一个闭区间，即[0, n - 1]。而当mid处的值不是目标值时，就要把mid从搜索区间中去除，继续在两边的某个闭区间中搜索。因此，左右指针的更新规则为left = mid + 1和right = mid - 1。

终止条件

搜索区间为空时就应该跳出循环

上面的代码中，while循环的条件是left <= right，也就是说当left == right + 1时跳出while循环。实际上，这个终止条件与前面说的闭区间相对应，当left == right时，闭区间内仍有一个索引的位置需要搜索；当left == right + 1时，[right + 1, right]已经是一个空集，意味着已经没有索引需要搜索了，因此就跳出循环。

开区间

爷就是喜欢开区间，那咋办嘛

开区间情况下，左右指针应初始化为left, right = 0, n，对应的搜索区间是一个开区间，即[0, n)。

• 当arr[mid] < target时，同样地，要把mid从搜索区间中去除，注意此时是开区间。于是left = mid + 1，对应的搜索区间为[mid + 1, right);
• 当arr[mid] > target时，right = mid， 对应的搜索区间为[left, mid)。

此时，while循环的条件应为left < right，也就是说当left == right时跳出while循环。对应的搜索区间为[left, left)，显然这个区间为空，即搜索完毕。完整代码如下。

def binarySearch(arr: List[int], target: int):
    n = len(arr)
    left, right = 0, n
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid
    return -1  # 没有找到，返回 -1

局限性

这个版本的二分查找至少还有两个需求无法满足：

• 如果target在数组中多次出现，我们想要找到它的左边界（即最早出现时的索引）或者右边界要怎么改呢？
• 如果target在数组中不出现，我们想要找到它插入到该数组中应该在的位置要怎么改呢？

寻找左侧边界

基于开区间版本，修改几个位置即可。

def binarySearch(arr: List[int], target: int):
    n = len(arr)
    if n == 0:  # 特判
    	return -1
    left, right = 0, n
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            right = mid  # 修改
        elif arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid
    return left  # 修改

代码还可以进一步简化，但是本文主要是为了弄清原理，这么写看起来更直观一些。基于这三处修改，我们来看看为什么这个版本可以返回左侧边界。

为什么需要特判

实际上也不是所有情况都需要特判，因为很多时候我们不会在空数组中搜索，那不是吃饱了撑的吗。主要是为了和返回的索引区分开来，避免返回值与空数组的情况发生混淆，具体往下看就明白了。

返回值的意义

这个版本的代码除了当target在数组中多次出现时返回它的左侧边界，它的返回值还有一个含义就是当前数组中比target小的元素个数。因此返回值的范围是[0, n]，如果没有特判，数组为空时也返回0，会发生混淆。

为什么可以找到左边界

关键在于这段代码：

if arr[mid] == target:
    right = mid

当找到target时，不返回索引，而是继续向左搜索，即在[left, mid)中搜索。

那么问题来了，如果此时mid已经是左边界了，继续在[left, mid)中搜索不会出错吗？事实上，每次左指针的更新规则为left = mid + 1且while循环的条件是left < right。也就是说最终仍然会搜索到[left, mid)，此时left == mid。

寻找右侧边界

基于上面的代码，修改一下就行。

def binarySearch(arr: List[int], target: int):
    n = len(arr)
    if n == 0:  # 特判
    	return -1
    left, right = 0, n
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            left = mid + 1  # 修改
        elif arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid
    return left - 1  # 修改

为什么要返回left - 1

注意到，当找到target时，不返回索引，而是继续向右搜索，left = mid + 1。因此，while循环结束时的左指针一定指向target右边的第一个元素。因此要返回left - 1。

寻找插入位置

上面提到，寻找左侧边界版本的返回值同样代表了数组中比target小的元素个数，索引不就来了吗？

def binarySearch(arr: List[int], target: int):
    n = len(arr)
    left, right = 0, n
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            right = mid  # 修改
        elif arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid
    return left  # 修改

需要注意的是，这里不需要特判，数组为空时直接往里放就完事了。

二分查找+所有细节保姆级详解(代码片段)

本文就来探究几个最常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。而且，我们就是要深入细节，比如不等号是否应该带等号，mid是否应该加一等等。分析这些细节的差异以及出现这些差异的... 查看详情

算法知识常用算法详解丨二分查找法（折半查找）(代码片段)

...是暴力解法：一次遍历，这时候时间复杂度是O(N),二分查找就是其中的一种优化，时间复杂度是O(logN);具体做法是一步一步逼近直到找到。前提是数组需要是一个排序数组。定义：二分查找也称折半查找（BinaryS... 查看详情

二分查找算法详解：快速查找的同时还最大程度的节省内存(代码片段)

...员面试策略（面试前的准备、面试中的技巧）请访问GitHub二分查找（BinarySearch）算法，也叫折半查找算法。二分查找的思想非常简单，很多非计算机专业的同学很容易就能理解，但是看似越简单的东西往往越难掌握好，想要灵活... 查看详情

文巾解题704.二分查找(代码片段)

1题目描述2解题思路二分查找见： 二分查找详解_刘文巾的博客-CSDN博客classSolution(object):defsearch(self,nums,target):left=0right=len(nums)-1while(left<=right):mid=left+(right-left)//2if(nums[mid]= 查看详情

stl二分算法(代码片段)

...upper_bound：查找第一个大于某个元素的位置。3.关于STL二分底层与自定义规则详解!!4.如何用STL二分查找范围内的上界和下界我是废物,搞了好久,感觉里面有哪里不太对,希 查看详情

stl二分算法(代码片段)

...upper_bound：查找第一个大于某个元素的位置。3.关于STL二分底层与自定义规则详解!!4.如何用STL二分查找范围内的上界和下界我是废物,搞了好久,感觉里面有哪里不太对,希 查看详情

❤️数据结构和算法动图演示，超详细，就怕你不会！二分查找详解建议收藏❤️(代码片段)

🎈作者：Linux猿🎈简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！🎈关注专栏：图解数据结构和算法（优... 查看详情

二分查找(代码片段)

69.Sqrt(x)(二分查找)35.SearchInsertPosition(二分查找)34.SearchforaRange33.SearchinRotatedSortedArray(二分查找)81.SearchinRotatedSortedArrayII74.Searcha2DMatrix(二分查找，剑指offer1) 查看详情

二分算法（java超详细）(代码片段)

文章目录目录文章目录一、二分查找1.整数二分1.1二分查找算法模板11.2二分查找算法模板21.3二分查找算法模板31.4二分查找算法模板41.5二分查找算法模板5练习题目+详解2. 浮点数二分总结一、二分查找1.整数二分二分查找࿱... 查看详情

二分查找(代码片段)

二分查找packagecom.zgz;importjava.lang.reflect.Array;importjava.util.Arrays;/***二分查找**@authorguozhenZhao*@date2019年4月8日*/publicclassBinarySearch/***要查找的数组必须是有序的*@paramkey*@paramarr*@return*/publicstatici 查看详情

二分查找(代码片段)

1. 二分查找算法概述二分查找是对一个有序数据集合所做的操作。超找开始时，首先找出有序集合中间的那个元素。如果此元素比要查找的元素大，就接着在较小的一半查找；反之，则在较大的一半查找。 2. 使用二... 查看详情

hiho36二分·二分查找二分查找(代码片段)

传送门:二分·二分查找分析ACCode1简洁ACCode2首先排序，然后再用原始的二分查找法，也行吧。OnlineACCode1#include<stdio.h>intmain(void)intn,k,ans=1,appeared=0,num;scanf("%d%d",&n,&k);while(n--)scanf("%d",&num);if(num<k 查看详情

二分查找算法(代码片段)

二分查找算法二分查找算法二分查找算法二分查找的前提是该数组是有序的二分查找的思路分析：首先确定该数组的中间的下标mid=(left+right)/2;然后让需要查找的数findValue和arr[mid]比较如果findValue>arr[mid],则说明你要查... 查看详情

java二分查找(代码片段)

查看详情

javajava二分查找(代码片段)

查看详情

二分法查找(代码片段)

目录二分法查找介绍二分法查找二分法的查找思路二分法有关示例解题思路代码实现二分法查找介绍二分法查找二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。时间复杂度：最坏情况查找... 查看详情

二分变种(代码片段)

你真的会写二分查找吗二分查找二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子... 查看详情

二分查找(代码片段)

素数判断递归二分查找循环二分查找一、判断一个数是否为素数素数：在大于1的自然数中，除了1和它本身，不再有其他因数的自然数intcheckNumber(intnumber)if(number<2)return0;for(inti=2;i<number;i++)if(number%i==0)return-1;return1;二、递归实... 查看详情