f*********m
发帖数: 726 | 1 不少方法都用到了binary search。设左右边界为l和r，边界中值为m。有些题用的是
while (l <= r),有的用的是while (l < r),m有的是m=l+(r-l)/2,有的是m=(l+r+1)/2
。挺晕的。
除了具体问题具体分析之外，有没有什么规律可循？ | K*****k
发帖数: 430 | 2 m = L + (R - L) / 2 可以防止L + R 超出整数范围
还有while (L + k < r)的，其中k是一个小整数，是为了可以提早退出，避免一些边界
条件
2
【在 f*********m 的大作中提到】
: 不少方法都用到了binary search。设左右边界为l和r，边界中值为m。有些题用的是
: while (l <= r),有的用的是while (l < r),m有的是m=l+(r-l)/2,有的是m=(l+r+1)/2
: 。挺晕的。
: 除了具体问题具体分析之外，有没有什么规律可循？
| K*****k
发帖数: 430 | 3 其实就是看：
至少还有几个元素的时候继续循环
标准的二分查找当然是至少还有一个元素，用while (L <= R)
但是有的变体，比如返回序号最大的或者最小的，修改L和R的时候可能导致死循环
比如L = 3, R = 4， M = 3，修改L或者R后，下次还是
L = 3, R = 4, M = 3
这样，就要用while (L + 1 < R), 至少还有三个元素的时候才继续循环，两个元素或
者一个元素的时候就该早点结束循环了。 | f*********m
发帖数: 726 | 4 大牛能否详细说说“返回序号最大的或者最小的“的原题是什么？
谢谢。
【在 K*****k 的大作中提到】
: 其实就是看：
: 至少还有几个元素的时候继续循环
: 标准的二分查找当然是至少还有一个元素，用while (L <= R)
: 但是有的变体，比如返回序号最大的或者最小的，修改L和R的时候可能导致死循环
: 比如L = 3, R = 4， M = 3，修改L或者R后，下次还是
: L = 3, R = 4, M = 3
: 这样，就要用while (L + 1 < R), 至少还有三个元素的时候才继续循环，两个元素或
: 者一个元素的时候就该早点结束循环了。
| l*****a
发帖数: 14598 | 5 sorted array,
given a target,
find the max index or min index if it is in the array
【在 f*********m 的大作中提到】
: 大牛能否详细说说“返回序号最大的或者最小的“的原题是什么？
: 谢谢。
| f*********m
发帖数: 726 | 6 多谢。
【在 l*****a 的大作中提到】
: sorted array,
: given a target,
: find the max index or min index if it is in the array
| w****x
发帖数: 2483 | 7
2
正常的都是 <= 吧， 要不会漏掉？， 我习惯写(l+r)/2, 说溢出的都是鸡蛋里挑骨头
了
【在 f*********m 的大作中提到】
: 不少方法都用到了binary search。设左右边界为l和r，边界中值为m。有些题用的是
: while (l <= r),有的用的是while (l < r),m有的是m=l+(r-l)/2,有的是m=(l+r+1)/2
: 。挺晕的。
: 除了具体问题具体分析之外，有没有什么规律可循？
| l*****a
发帖数: 14598 | 8 how about those who mentioned that
(l+r)>>1 is faster than (l+r)/2
【在 w****x 的大作中提到】
:
: 2
: 正常的都是 <= 吧， 要不会漏掉？， 我习惯写(l+r)/2, 说溢出的都是鸡蛋里挑骨头
: 了
| t*********h
发帖数: 941 | 9 how about L/R=M+1?
【在 K*****k 的大作中提到】
: 其实就是看：
: 至少还有几个元素的时候继续循环
: 标准的二分查找当然是至少还有一个元素，用while (L <= R)
: 但是有的变体，比如返回序号最大的或者最小的，修改L和R的时候可能导致死循环
: 比如L = 3, R = 4， M = 3，修改L或者R后，下次还是
: L = 3, R = 4, M = 3
: 这样，就要用while (L + 1 < R), 至少还有三个元素的时候才继续循环，两个元素或
: 者一个元素的时候就该早点结束循环了。
|
|
