type
status
date
slug
summary
tags
category
icon
password
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 可以替代的就是
中的判断
假设我们要从 平方后的lis里找 a的平方
这里key 返回值为if判断 即决定什么情况看前半部分
同时要注意这里就不用放 搜索目标 作为参数了
放在key里做判断就行
也是因为这种写法 以后binary search可以默认先对 目标是否小于mid 做判断
附上一些leetcode案例
69.Sqrt(x)
74. Search a 2D Matrix
这里利用了刚才发现的规则 如果搜索到 bisect_left 和 right才会不一样
否则一致 可以用来比较是否搜索到
参考：
- Author:ran2323
- URL:https://www.blueif.me//article/14671a79-6e22-80e9-b97e-c92b69bb3c93
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
