ylink's Nest

二分查找专题加强

今天终于找到适合自己的方法去征服任何(任何!)写二分查找的题目的方式了。记录如下:

对任意一个二分查找的代码场景,写的时候可以套这个模板思考:

  • 要返回无效状态(如返回值-1)的,则循环条件是l <= r(因为l > r时才不可能存在查找的区间,此时返回无效状态在情理之中)。如果时类似upper_bound、lower_bound这种不会返回无效状态的,则循环条件是l < r(因为如果不存在时,l == r时的位置也就是我们求解的位置)
  • 首先明确要写的二分查找的需求,然后思考:对每一个给定的mid值,若nums[mid] < target,则……(要找的位置在左侧,还是有可能包括此位置或左侧等等);若nums[mid] > target,则……;若nums[mid] == target,则……(有可能还要分情况讨论,比如找target第一次、最后一次出现的位置的题目),然后转化成代码即可。
  • 牢记mid的运算式和两点优势:mid = left + (right – left) / 2,优点有迭代器不支持加法运算和防止加法运算的结果溢出。

第二步附范例图如下:

4 评论

  1. lower_bound和upper_bound当然能返回无效状态,写二分根本不需要分情况讨论,是你自己不会

    • ylink

      19/10/01 在 19:24

      那可否麻烦你发一份相关教程,我也学习一下呢。我参照《算法笔记》看的二分的内容,那里面的章节确实没有你说的xxx_bound返回错误值方法的讨论。

    • ylink

      19/10/01 在 19:38

      不对呀,假设我们讨论的是非降序序列,lower_bound的定义是如果给定的target存在,那么返回第一个target在序列中的index;如果序列中不存在target,那么返回假设target存在,它在序列中应该在的位置。按照这个定义的话,为啥要返回错误码?还是我把lower_bound定义理解错了?upper_bound以此类推。

      • 你要考虑如果是找某个数的后继或者前驱的话,mid 两种情况分别是取不到 r 和 l 的;因为你要根据 mid 的值来更新 l 或 r 的位置,mid 总会跟 l 或r 相差 1 ,这个过程就可能造成 r 或 l 越界到 (r+1) 或 (l-1) 的位置上,接着下一轮循环就会在这个越界位置上结束,此时就是无效状态。
        至于你前面说的那个返回假设 target 在的话,它应该在的 index,我觉得这个说法不是十分妥当,因为你没明确定义“它应该在的 index ”是在哪儿,比如我可以说“它应该在的 index ”不是一个int之类的…

发表评论

6 + 10 =