由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - binary search什么时候用l
相关主题
有没有人总结过binary search是mid加减1和小于或者等于的情况分类问一道CareerCup里的题目
A Simple Question on Binary Search给定一个值和sorted队列,找到所有pair(其和等于给定值)
binary search in rotated sorted array有重复时怎么办?Google电面题
解题速度啥要求刚面完 google,题目
binary search的更新和边界问题fb店面
Ebay 三轮skype面筋(免onsite Offer)谁能解释下careerUp上18.3这题吗?
binary search里面你们是用 < 还是<=问个电面题
Search in a sorted, rotated listleetcode 中部分binary search 总结
相关话题的讨论汇总
话题: mid话题: binary话题: num话题: val话题: search
进入JobHunting版参与讨论
1 (共1页)
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()函数。
1 (共1页)
进入JobHunting版参与讨论
相关主题
leetcode 中部分binary search 总结binary search的更新和边界问题
问个经典问题的improvementEbay 三轮skype面筋(免onsite Offer)
google 电面binary search里面你们是用 < 还是<=
问大家关于编程的经验Search in a sorted, rotated list
有没有人总结过binary search是mid加减1和小于或者等于的情况分类问一道CareerCup里的题目
A Simple Question on Binary Search给定一个值和sorted队列,找到所有pair(其和等于给定值)
binary search in rotated sorted array有重复时怎么办?Google电面题
解题速度啥要求刚面完 google,题目
相关话题的讨论汇总
话题: mid话题: binary话题: num话题: val话题: search