算法篇————二分查找算法

        

2016-09-18

二分查找算法总结

  1. 典型的二分查找
  2. 复杂度低的二分查找
  3. 例子

    典型的二分查找

    给一个已经排序的已知的数组A[N],在最短的时间内找到其中的一个元素。下面给出最典型的二分查找算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
int BinarySearch(int A[],int l,int r,int key){
int m;
while( l <= r ){
m = ( l + r ) / 2;
if( A[m] == key ) // 第一次比较
return m;
if( A[m] < key ) // 第二次比较
l = l + 1;
else
m = m - 1;
}
return -1; // 为查找到该元素返回-1
}

理论上,我们最多需要 logN+1 次比较。仔细观察,我们在每次迭代中使用两次比较,除了最后比较成功的一次。实际应用上,比较也是代价高昂的操作,往往不是简单的数据类型的比较。减少比较的次数也是优化的方向之一。


复杂度低的二分查找

下面是一个比较次数更少的实现:
需要注意的,要保证我们恒等式(A[l] <= key & A[r] > key)正确,后面还会用到循环不变式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 循环不变式: A[l] <= key & A[r] > key
// 边界: |r - l| = 1
// 输入: A[l .... r-1]
int BinarySearch(int A[],int l,int r,int key){
int m;
while( r - l > 1 ){
if( A[m] <= key )
l = m ;
else
r = m ;
}
if( A[l] == key )
return l ;
else
return -1 ;
}


例子描述

给一个有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,这是最坏的情况根据下面的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 循环不变式: A[l] <= key and A[r] > key
// 边界条件: |r - l| = 1
// 输入: A[l .... r-1]
// 先决条件: A[l] <= key <= A[r]
int Floor(int A[], int l, int r, int key)
{
int m;
while( r - l > 1 )
{
m = l + (r - l)/2;
if( A[m] <= key )
l = m;
else
r = m;
}
return A[l]; // A[l]即是小于或等于key的最大元素
}
// 初始调用
int Floor(int A[], int size, int key)
{
// 如果 key < A[0] 不符合条件
if( key < A[0] )
return -1;
return Floor(A, 0, size, key);
}