帮忙推荐一款流量控制软件# Hardware - 计算机硬件
d*w
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
挑战的：-), 需要小心的是区间的开闭，取中点是否会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
