分享一个看到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

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

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

二分查找有几种写法？它们的区别是什么？ - 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