h*****y 发帖数: 218 | 1 我还看到
while( l + 1 < r)
这种是一种习惯,还是背后都有不同的考量?哪位大牛来说说? |
C******8 发帖数: 501 | 2 always check your loop invariant
【在 h*****y 的大作中提到】 : 我还看到 : while( l + 1 < r) : 这种是一种习惯,还是背后都有不同的考量?哪位大牛来说说?
|
m******0 发帖数: 222 | 3 这么背是不行的。比如题目让你在num数组里二分找到大于给定值val的第2小的那个数
,你怎么背都不行
基本原则就一个:
给定左右范围L,R,计算中间值M,看num[M]是否为target。是则返回,否,则判断
target在M左边还是右边。另外终止条件复杂的时候,用while(1)比较好,判断break在
里面做
按照上面的题举例:
// num[], val
int L,R
while (1) {
int M=(L+R)/2; //or R-(R-L)/2
// 判断M是否为target, 一共只有下面两种情况:
if ((M==1 && num[M]>val && num[M-1]>val) ||
(M>1 && num[M]>val && num[M-1]>val && num[M-2]<=val))
return M;
if (num[M] <= val) // 若存在target,必然在M右面
L=M+1;
else // 否则就在M左边
R=M-1;
if (L > M)
return -1; // 左右边界已经交叉,不可能找到target了
} |
h*****u 发帖数: 109 | 4 这是很好的问题。看起来简单。
binary search 如果用 while(l < r)那么结束时有可能l = r。所以你还要判断一次。
不能直接return false. 所以用while(l <= r)好。注意l = mid + 1如果换成l = mid
可能deadlock. 同理r也是如此。
如果在rotated array里找最小值。用while(l < r)好。最后点l=r就是最值
对于这种ordered structure (sorted array, bst, sqrt(对应函数是平方),正整数
divide)都可以用binary search。 binary search的更本质的想法是region
elimination on sorted structure. 你用这个理解,什么first occurrence of an
element等就好懂了。 |
l*****a 发帖数: 14598 | 5 这种写法是避免如下情况
if(target>=a[mid]) {
l=mid;
} else {
...
}
u can see that if l==r-1
mid will always be l, then ...
感觉上这种题主要看你的两分之后的动作来决定你的终止条件
是lo=mid/hi=mid
还是lo=mid+1/hi=mid-1
【在 h*****y 的大作中提到】 : 我还看到 : while( l + 1 < r) : 这种是一种习惯,还是背后都有不同的考量?哪位大牛来说说?
|
r*****0 发帖数: 38 | 6 我一般这么写
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
ans = l;;
始终保证答案在[l, r), 根据需要只用改check()函数。 |