讨论/《二分查找》 - 二分查找模板分析/
《二分查找》 - 二分查找模板分析
共 5 个回复

举例而言

  1. 在严格递增有序数组中寻找某个数
  2. 在有序数组中寻找某个数第一次出现的位置(或者在有序数组中寻找第一个大于等于某个数的位置)
  3. 已知有一个先严格递增后严格递减的数组,找数组最大值的位置

实际上在解题时,一般前两种模板就足够了(大部分应用第三种模板的情况都可以转化为前两种),第二种的模板和 Python 中 bisect.bisect() 类似。

8

确实了解一下总结的模版很有帮助,但感觉实际解题还是不能靠背,还是要举例子然后手动推算一下来确定边界。

4

看了一下,只会1和2,1用于查找某个一定存在的元素,2用于查找插入元素的位置,3是什么情况用?

4

同只会1和2, 感觉3用不上。
while(l<=r)
适用于中间会产生结果,比如求平方根,中间每一步都是结果,最后l>r之前的一步结果为最后结果
while(l<r)
适用于夹逼出唯一一个结果,如果求峰值,峰值一定存在,那么只要夹逼出l=r的情况就是结果。

3

mark