d********w
发帖数: 363 | 1 binary search是最经典的算法之一，编程珠玑上说只有10%的人能写对，看来还是很有
挑战的：-), 需要小心的是区间的开闭，取中点是否会overflow, 确定新upperbound和
lowerbound的范围，会不会死循环
其实还可以衍生其他问题，比如：
1）如果找不到元素，返回应该插入的位置
2）如果数组允许有重复，寻找最小的那个i，使得arr[i] = v， （第一次出现的位置）
3）如果数组允许有重复，寻找最大的那个i，使得arr[i] = v
4）如果数组允许有重复，寻找最小的那个i，使得arr[i] > v
5）如果数组允许有重复，寻找最大的那个i，使得arr[i] < v
6）给2个有序数组，大小一致，如何求他们的median
7）循环数组的二分查找
欢迎大家补充，除了最后2个，其他不难，但是要保证没有bug就需要多练了。
参考资料：
http://en.wikipedia.org/wiki/Binary_search
Programing pearls: Ch4, Ch9.3 | i**********e
发帖数: 1145 | 2 还有一个要补充的，就是一个 rotated 排序好的数组寻找一个值。面试经常会考察，
必定要多多练习：
什么是 rotated 的数组呢？
例如：
[0 1 2 4 5 6 7]
以上排序好的数组往左移动 3 位，就变成以下的数组。
[4 5 6 7 0 1 2]
应该怎样才能在这数组里进行搜索呢？
http://www.ihas1337code.com/2010/04/searching-element-in-rotate | P********l
发帖数: 452 | 3 我收集的一些题，有的还没有答案.
http://www.sureinterview.com/lstqst#/tag/154001
请给点反馈和建议，不胜感激。
(算法题答案属原创。如果想转载，请跟我联系） | d********w
发帖数: 363 | 4 刚才看了一下programming pearls 9.3,
找第一次出现数字的位置，书中给出的优雅解法：
int search(int x[], int n, int t) {
int l = -1;
int u = n;
int m = 0;
while (l+1 != u) {
/* invariant : x[l] < t && x[u] >= t && l < u */
m = (l+u)/2;
if (x[m] < t)
l = m;
else
u = m;
}
assert(l+1 == u && x[l] =t);
int p = u;
if (p>=n || x[p] != t)
p = -1;
return p;
}
这里的invariant意味深长，x[u] >= t 这样可以避免多余的比较
对比经典的二分写法，大体上可以得出个规律，
1) 如果l,u的起始区间是0，n-1, while的条件为l<=u，在二分时候使用m+1,m-1赋值;
2) 如果l, u的起始区间是-1，n, while的条件为l
欢迎大家指正
【在 i**********e 的大作中提到】
: 还有一个要补充的，就是一个 rotated 排序好的数组寻找一个值。面试经常会考察，
: 必定要多多练习：
: 什么是 rotated 的数组呢？
: 例如：
: [0 1 2 4 5 6 7]
: 以上排序好的数组往左移动 3 位，就变成以下的数组。
: [4 5 6 7 0 1 2]
: 应该怎样才能在这数组里进行搜索呢？
: http://www.ihas1337code.com/2010/04/searching-element-in-rotate
| P********l
发帖数: 452 | 5 找起始位置的关键是找到之后不要跳出来。把这个位置处理成找到较大值。二分还是比
较重要的。
binary search for a range:
http://www.sureinterview.com/shwqst/545001/154001
【在 d********w 的大作中提到】
: 刚才看了一下programming pearls 9.3,
: 找第一次出现数字的位置，书中给出的优雅解法：
: int search(int x[], int n, int t) {
: int l = -1;
: int u = n;
: int m = 0;
: while (l+1 != u) {
: /* invariant : x[l] < t && x[u] >= t && l < u */
: m = (l+u)/2;
: if (x[m] < t)
|
|
