分享一个看到binary search 的模板

有一个binary search 101的帖子也很好。

yyz20002008 发表于 2022-5-4 12:56
某章的 模板最后double check的时候 还是不太明白怎么想的先返回start再返回end if A[start] = target retu ...

最后答案要么在start要么在end。你需要找左边界，就先查start，再查end。反之相反。如果只是找答案，不在乎左右，那顺序无所谓。

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

假设有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
说起二分法的模板还真是没有哪家比的过九章的，永远不会死循环，而且到现在还没忘记😂

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

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

这个模板太强了 就是面试的时候万一问以来解释起来有点麻烦😢

这个帖子已经不在了哎
哪位大佬有备份吗

DLer 发表于 2022-5-29 14:55
这个帖子已经不在了哎
哪位大佬有备份吗

看这个试试 https://leetcode.com/problems/ko ... lved-many-problems.

spiritcat 发表于 2022-5-4 10:41
常用的需要两个模版，二分查找需要数据具有二段性。

假设有x为false，o为true。

如果列表只剩两个元素, 而且想保留左指针指向的元素:
   使用常规的“mid = (left + right) // 2; left = mid” 就会陷入死循环
   如果只剩两个元素, 再把mid指向第靠右的元素(mid = (left + right + 1) // 2)就可以完美解决这个问题