我们都知道二分查找算法，实际上二分查找以及其扩展应用是很广泛的。这里收集了一些和二分查找有关的有趣问题。强烈建议大家看完问题后最小化浏览器，先尝试自己去解决，然后再看代码，问题都不是太难。
问题1描述
给一个已经排序的数组，其中有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）正确，后面还会用到循环不变式。
问题2描述
给一个有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 函数
问题3描述
给一个有重复元素的已排序数组，找出给定的元素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
|
}
|
问题4描述
有一个已排序的数组（无相同元素）在未知的位置进行了旋转操作，找出在新数组中的最小元素所在的位置。
例如：原数组 {1,2,3,4,5,6,7,8,9,10}， 旋转后的数组可能是 {6,7,8,9,10, 1,2,3,4,5 }，也可能是 {8,9,10,1,2,3,4,5,6,7 }
分析：
我们不断的缩小 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
|
}
|