关于Binary Search的疑惑

找个讲得比较好得大神，然后主要练习一种模板去理解：
https://www.youtube.com/watch?v=e-UALGfQpOk&feature=youtu.be

古城 发表于 2021-7-12 13:29
字数字数

看过你的视频，很有用

Leetcode 上面有一个很好的帖子, google直接搜leectode binary search 101
第一个就是
讲的特别好,看完之后binary search从此没烦恼

oicq455669 发表于 2021-7-13 07:03
关键是想不清这些模板是咋回事。。。

第一次用可以走几个test case, 看看跳出条件是什么，left right跳出后的相对关系是什么。
之后我觉得只用一个板子可以直接用了。二分法实际上就是猜答案，猜高了我们就往低猜，不断逼近答案

我是你哥哥 发表于 2021-7-12 20:40
https://www.youtube.com/watch?v=J-IQxfYRTto&t=310s

谢谢，看了这个视频很有帮助

Liyukuang 发表于 2021-7-12 17:13
我也有过这个疑惑，解决方案是永远只用 while left

分析的很详细，很有帮助

ALWAYS use "one past last"

可以看一下cpp的类似的代码

https://en.cppreference.com/w/cpp/algorithm/lower_bound

我来说一个理论上最最最简单的记法（wiki上的解法），记一个知识点覆盖所有情况：
二分查找就是找序列中有多少个元素严格小于（或小于）target

求左边界（同样适用于序列元素无重复的情况）
L: 序列中至少有多少个<target的元素
R:序列中至多有多少个<target的元素

求右边界
L: 序列中至少有多少个<=target的元素
R:序列中至多有多少个<=target的元素

以下的不用记，记住上面的定义可以轻松推出来：

以左边界为例
0.初始化，因为是元素的个数，根据定义L=0 R=N
1. while (L<R): 如果L>=R，则已经找到了答案的上下界
2. arr[mid] < target，至少有mid+1个小于target（mid和mid左边的元素都小于target），L=mid+1
3. arr[mid] >= target，至多有mid个元素小于target(mid和mid右边的元素都大于等于target)，R=mid

右边界的情况代码一样，除了不等号换成小于等于

最后求出答案后，根据一个元素的下标等于它左边的元素的个数，即可得出下标

求加米～

楼上就回答的很详细了，我就单单说一下你困惑的这个点
其实只要考虑到到底遍历的时候是右闭还是右开区间就好了
如果是【left, right】右闭，那么停止条件就是left>right，因此while需要（left<=right），不然mid就少算了一个mid=left=right的情况。 这样想的话，right = mid-1等等就显而易见了，因为是闭区间
【left, right）开区间的时候同理，但是这个时候的终止条件变成left=right（开区间不能取值）了，所有的改动就是基于这个

我以前也经常搞混，经常要找很多test case试试到底返回什么。自从看了这个帖子就把里面的原理搞懂了。楼主可以看一下 https://github.com/yuzhoujr/leetcode/issues/8