L***s
发帖数: 1148 | 1 Suppose A is sorted array of integers,
a0 and a1 are integers (a0 <= a1).
Write a binary search algorithm to find
the first (or the last) element A[i] such that
1) a0 <= A[i]
2) a0 < A[i]
3) A[i] <= a1
4) A[i] < a1
5) a0 <= A[i] <= a1
6) a0 < A[i] < a1
7) a0 <= A[i] < a1
8) a0 < A[i] <= a1
还没算“==”的情况，就已经有16种变化了，一不小心就写错。
在 mid=(low+high)/2 中，你们的(low,high)是统一取闭区间、
左开右闭区间、还是左闭右开区间？还说说对上面16种不同的问法取不同的开闭策略？ |
l*********8
发帖数: 4642 | 2 基本的就1,2两种。 其他可以由1,2变化而来。 |
q*****w
发帖数: 62 | 3 1,2,3,4可以组合成5,6,7,8. 下面这篇讲了如何用14行代码囊括1,2,3,4种情况。
http://fihopzz.blogspot.com/2013/07/enter-post-title-here-binar
stackoverflow上也有类似的帖子。你也可以自己找找。 |
A*********c
发帖数: 430 | 4 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
看这个。
【在 L***s 的大作中提到】
: Suppose A is sorted array of integers,
: a0 and a1 are integers (a0 <= a1).
: Write a binary search algorithm to find
: the first (or the last) element A[i] such that
: 1) a0 <= A[i]
: 2) a0 < A[i]
: 3) A[i] <= a1
: 4) A[i] < a1
: 5) a0 <= A[i] <= a1
: 6) a0 < A[i] < a1
|
g***x
发帖数: 45 | 5 记住这2段代码就可以了
http://www.cplusplus.com/reference/algorithm/binary_search/
http://www.cplusplus.com/reference/algorithm/lower_bound/
【在 L***s 的大作中提到】
: Suppose A is sorted array of integers,
: a0 and a1 are integers (a0 <= a1).
: Write a binary search algorithm to find
: the first (or the last) element A[i] such that
: 1) a0 <= A[i]
: 2) a0 < A[i]
: 3) A[i] <= a1
: 4) A[i] < a1
: 5) a0 <= A[i] <= a1
: 6) a0 < A[i] < a1
|
d******g
发帖数: 38 | 6 这个正解，当然还有upper_bound
基本上有2大类，early/deferred equality detection
如果有重复元素并且要求upper/lower bound只能用deferred
upper和lower代码的主要区别就在于判断是否update右边界的时候用<还是<=
区间的问题其实只是如何实现的问题，通常都是左右闭区间，但是我喜欢左闭右开
区间的选择只会影响你的循环终止条件、边界update，和算法核心无关
曾经我也和lz一样迷茫，仔细看了一下发现binary search原来如此精妙
记忆中国内的教材根本没有讲的这么仔细，还是看wiki吧
http://en.wikipedia.org/wiki/Binary_search_algorithm
【在 g***x 的大作中提到】
: 记住这2段代码就可以了
: http://www.cplusplus.com/reference/algorithm/binary_search/
: http://www.cplusplus.com/reference/algorithm/lower_bound/
|
