本文共 3734 字，大约阅读时间需要 12 分钟。
我们都知道二分查找算法，实际上二分查找以及其扩展应用是很广泛的。这里收集了一些和二分查找有关的有趣问题。强烈建议大家看完问题后最小化浏览器，先尝试自己去解决，然后再看代码，问题都不是太难。
给一个已经排序的数组，其中有N个互不相同的元素。要求使用最小的比较次数找出其中的一个元素。(你认为二分查找在排序数组里找一个元素是最优的算法的吗？)
不需要太多的理论，这是一个典型的二分查找算法。先看下面的代码：
01 | // 返回要查找元素的下标，-1为没有找到 |
02 | int BinarySearch(int A[], int l, int r, int key) |
03 | { |
04 | int m; |
05 | while( l <= r ) |
06 | { |
07 | m = l + (r-l)/2; |
08 |
09 | if( A[m] == key ) //第一次比较 |
10 | return m; |
11 |
12 | if( A[m] < key ) // 第二次比较 |
13 | l = m + 1; |
14 | else |
15 | r = m - 1; |
16 | } |
17 |
18 | return -1; |
19 | } |
理论上，我们最多需要 logN+1 次比较。仔细观察，我们在每次迭代中使用两次比较，除了最后比较成功的一次。实际应用上，比较也是代价高昂的操作，往往不是简单的数据类型的比较。减少比较的次数也是优化的方向之一。
下面是一个比较次数更少的实现：
01 | // 循环不变式： A[l] <= key & A[r] > key |
02 | // 边界: |r - l| = 1 |
03 | // 输入: A[l .... r-1] |
04 | int BinarySearch(int A[], int l, int r, int key) |
05 | { |
06 | int m; |
07 | while( r - l > 1 ) |
08 | { |
09 | m = l + (r-l)/2; |
10 |
11 | if( A[m] <= key ) |
12 | l = m; |
13 | else |
14 | r = m; |
15 | } |
16 | if( A[l] == key ) |
17 | return l; |
18 | else |
19 | return -1; |
20 | } |
在while循环中，我们仅依赖于一次比较。搜索空间( l->r )不断缩小，我们需要一个比较跟踪搜索状态。
需要注意的，要保证我们恒等式（A[l] <= key & A[r] > key）正确，后面还会用到循环不变式。
大家可以在这个链接看到上面代码的测试：
给一个有N个互不相同的元素的已排序数组，返回小于或等于给定key的最大元素。 例如输入为 A = {-1, 2, 3, 5, 6, 8, 9, 10} key = 7,应该返回6.
分析：
我们可以用上面的优化方案，还是保持一个恒等式，然后移动 左右两个指针。最终 left指针会指向 小于或等于给定key的最大元素(根据恒等式A[l] <= key and A[r] > key)。
- > 如果数组中所有元素都小于key，左边的指针left 会一直移动到最后一个元素。
- > 如果数组中所有元素都大于key，这是一个错误条件，无答案。
- > 如果数组中的所有元素都 <= key，这是最坏的情况根据下面的实现
代码：
01 | // 循环不变式: A[l] <= key and A[r] > key |
02 | // 边界条件: |r - l| = 1 |
03 | // 输入: A[l .... r-1] |
04 | // 先决条件: A[l] <= key <= A[r] |
05 | int Floor(int A[], int l, int r, int key) |
06 | { |
07 | int m; |
08 | while( r - l > 1 ) |
09 | { |
10 | m = l + (r - l)/2; |
11 | if( A[m] <= key ) |
12 | l = m; |
13 | else |
14 | r = m; |
15 | } |
16 | return A[l]; |
17 | } |
18 |
19 | // 初始调用 |
20 | int Floor(int A[], int size, int key) |
21 | { |
22 | // 如果 key < A[0] 不符合条件 |
23 | if( key < A[0] ) |
24 | return -1; |
25 |
26 | return Floor(A, 0, size, key); |
27 | } |
在这个链接可以看到相应的测试： .
这个函数在C++的STL里面有实现 : lower_bound 函数
给一个有重复元素的已排序数组，找出给定的元素key出现的次数，时间复杂度要求为logN.
分析
其实可以对上面的程序稍作修改，思路就是分别找出key 第一次出现的位置和最后一次出现的位置。
01 | // 输入: 数组区间 [l ... r) |
02 | // 循环不变式: A[l] <= key and A[r] > key |
03 | int GetRightPosition(int A[], int l, int r, int key) |
04 | { |
05 | int m; |
06 | while( r - l > 1 ) |
07 | { |
08 | m = l + (r - l)/2; |
09 | if( A[m] <= key ) |
10 | l = m; |
11 | else |
12 | r = m; |
13 | } |
14 | return l; |
15 | } |
16 |
17 | // 输入: 数组区间 (l ... r] |
18 | // 恒等式: A[r] >= key and A[l] > key |
19 | int GetLeftPosition(int A[], int l, int r, int key) |
20 | { |
21 | int m; |
22 | while( r - l > 1 ) |
23 | { |
24 | m = l + (r - l)/2; |
25 | if( A[m] >= key ) |
26 | r = m; |
27 | else |
28 | l = m; |
29 | } |
30 | return r; |
31 | } |
32 |
33 | int CountOccurances(int A[], int size, int key) |
34 | { |
35 | // 找出边界 |
36 | int left = GetLeftPosition(A, -1, size-1, key); |
37 | int right = GetRightPosition(A, 0, size, key); |
38 |
39 | // key有可能不存在，需要判断 |
40 | return (A[left] == key && key == A[right])? |
41 | (right - left + 1) : 0; |
42 | } |
测试程序：.
有一个已排序的数组（无相同元素）在未知的位置进行了旋转操作，找出在新数组中的最小元素所在的位置。
例如：原数组 {1,2,3,4,5,6,7,8,9,10}， 旋转后的数组可能是 {
分析：
我们不断的缩小 l 左指针和 r 右指针直到有一个元素。把上面划横线的作为第一部分，剩下的为第二部分。如果中间位置m落在第一部分，即A[m] < A[r] 不成立，我们排序掉区间 A[m+1 ... r]。 如果中间位置m落在第二部分，即 A[m]<A[r]成立，我们缩小区间至 A[m+1 .... r ]。 直到搜索的区间大小为1就结束。
01 | int BinarySearchIndexOfMinimumRotatedArray(int A[], int l, int r) |
02 | { |
03 | int m; |
04 |
05 | // 先决条件: A[l] > A[r] |
06 | if( A[l] <= A[r] ) |
07 | return l; |
08 |
09 | while( l <= r ) |
10 | { |
11 | //终止条件 |
12 | if( l == r ) |
13 | return l; |
14 |
15 | m = l + (r-l)/2; // 'm' 可以落在第一部分或第二部分 |
16 |
17 | if( A[m] < A[r] ) |
18 | // (m < i <= r),可以排除 A[m+1 ... r] |
19 | r = m; |
20 | else |
21 | // min肯定在区间 (m < i <= r), |
22 | // 缩小区间至 A[m+1 ... r] |
23 | l = m+1; |
24 | } |
25 | return -1; |
26 | } |
27 |
28 | int BinarySearchIndexOfMinimumRotatedArray(int A[], int size) |
29 | { |
30 | return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1); |
31 | } |
测试程序：.
后续文章中讲继续使用二叉搜索来解决几个有趣的问题，欢迎大家的评论。
ACM之家原创，链接：
转载地址：http://iwolf.baihongyu.com/