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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还有一个要补充的,就是一个 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才看了一下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)
|
|