分享一个看到binary search 的模板

很多刷题的人，尤其上过各种培训机构的 可能都知道一个binary search的模板
这个是我在leetcode上看到的 讲的挺好
欢迎大家在下面讨论 分享你知道的模板 （如果你曾经仔细研究过 终止条件 小于 还是小于等于， 是等于mid 还是mid 加1 减1什么的）
https://leetcode.com/discuss/gen ... olved-many-problems

常用的需要两个模版，二分查找需要数据具有二段性。

假设有x为false，o为true。
情形1:[xxxxxxooooooo]，查找第一个True/o的位置，即查找左边界
while l<r:
  m = (l+r)//2
  if check(m):
     r = m
  else:
    l = m + 1

情形2:[oooooxxxxxxxx]，查找最后一个True/o的位置，即查找右边界
while l<r:
  m = (l+r+1)//2
  if check(m):
     l = m
  else:
    r = m - 1

说起二分法的模板还真是没有哪家比的过九章的，永远不会死循环，而且到现在还没忘记😂

xCookies 发表于 2022-5-4 12:44
说起二分法的模板还真是没有哪家比的过九章的，永远不会死循环，而且到现在还没忘记😂

但是某章的模板 解释起来很费劲 面试官要是问你 你为什么这么写 怎么回答
难道我长期刷题总结出来的？

二分查找有几种写法？它们的区别是什么？ - Jason Li的回答 - 知乎
https://www.zhihu.com/question/36132386/answer/530313852

插个眼zszs

有个叫五点七线的油管博主也总结了一个万能二分查找公式并且用数学方法验证了其可行性，很不错可以去看看

插个眼zszs

大咪咪长得胖 发表于 2022-5-4 10:52
有个叫五点七线的油管博主也总结了一个万能二分查找公式并且用数学方法验证了其可行性，很不错可以去看看

谢谢分享！
纠正一个typo，刚搜了一下，这个博主好像叫“五点七边”，内容做得挺清晰的，再次感谢

httpama 发表于 2022-05-04 09:32:25
谢谢分享！
纠正一个typo，刚搜了一下，这个博主好像叫“五点七边”，内容做得挺清晰的，再次感谢

哈哈哈 对对 我打错了

马克一下zszszs

谢谢分享

某章的 模板最后double check的时候 还是不太明白怎么想的先返回start再返回end if A[start] = target return start if A[end] == target return end