bisect in python(基础库的二分查找)

bisect的基本用法

返回的是insertion point

bisect_left 和 right的区别在于

如果搜索成功

left最后返回的位置 就是值所处的位置 可以直接insert

而 right返回 值右侧的位置 也就是left+1 使得 a[:i] 包含值

同样可以直接insert

如果未搜索到完全一样(搜索失败) 全部返回 比值大的第一位置

此时 a[:i] 包含值

举个例子 如果用来做成绩查询在哪个档位

那么有4个数 可以产生5个档

这里的key 重点说一下 可以用来快速做判断

注意这个是3.10版本才更新的

我们先手写一个search 这里将会是bisect_left

这种写法会有别于 一般return mid的做法 即便搜索失败也可以返回

小于或等于a的最大index

那么key 可以替代的就是

if a >= lis[mid]:
		low = mid + 1

中的判断

假设我们要从 平方后的lis里找 a的平方

这里key 返回值为if判断 即决定什么情况看前半部分

同时要注意这里就不用放 搜索目标 作为参数了

放在key里做判断就行

也是因为这种写法 以后binary search可以默认先对 目标是否小于mid 做判断

附上一些leetcode案例

69.Sqrt(x)

74. Search a 2D Matrix

这里利用了刚才发现的规则 如果搜索到 bisect_left 和 right才会不一样

否则一致 可以用来比较是否搜索到

参考：

https://www.cnblogs.com/breakyizhan/p/13263440.html

https://fanchenbao.medium.com/full-powered-binary-search-with-bisect-in-python-3-10-fb4a76110746#:~:text=Although we can do binary,list and the target value.