谈二分查找实现与改进

翻开C数据结构一书，第二章有一个经典的二分查找示例程序：
typedef int ElementType;
#define NotFound (-1)
/* START: fig2_9.txt */
int
BinarySearch( const ElementType A[ ], ElementType X, int N )
{
int Low, Mid, High;
/* 1*/ Low = 0; High = N - 1;
/* 2*/ while( Low <= High )
{
/* 3*/ Mid = ( Low + High ) / 2;
/* 4*/ if( A[ Mid ] < X )
/* 5*/ Low = Mid + 1;
else
/* 6*/ if( A[ Mid ] > X )
/* 7*/ High = Mid - 1;
else
/* 8*/ return Mid; /* Found */
}
/* 9*/ return NotFound; /* NotFound is defined as -1 */
}
提一个问题，如果有一个10大小的数组顺序存有0-9个整数，你觉得用上面二分查找找到这10个数，分别用了多少次循环？比如查找0元素和9元素?，我们来写一段程序进行验证：
#include <stdio.h>
int count = 0; //循环次数
template<typename T>
int binary_find(T * A, size_t N, T x)
{
int low = 0, mid, high= N-1;
while(low <= high)
{
mid = (low + high) >> 1;
if(A[mid] == x) return mid;
if(A[mid] < x)
low = mid + 1;
else
high = mid - 1;
++count;
}
return -1;
}
//测试程序
int main()
{
int i, size = 10;//6, 9, 13, 16 19 23(5, 8, 11, 15, 18, 21) //10到1000万数据最大查找次数
int *arr = new int[size];
for(i = 0; i < size; ++i)
arr[i] = i;
int x , max = 0;
for(i = 0; i < size; ++i){
x = binary_find(arr, size, i);
//x = bfind(arr, size, i);
if(x == -1)
puts("not found");
else
printf("found %d: count %d\n", arr[x], count);
if(max < count)
max = count;
count = 0;
}
printf("max =%d\n", max);
delete[] arr;
}
----------------------------------------
运行结果：
found 0: count 2
found 1: count 1
found 2: count 2
found 3: count 3
found 4: count 0
found 5: count 2
found 6: count 3
found 7: count 1
found 8: count 2
found 9: count 3
max =3
看到了吧，查找某元素循环次数最大是3, 我们再看看数组为100时的情况，将size改成100;
found 0: count 5
found 1: count 6
found 2: count 4
found 3: count 5
found 4: count 6
found 5: count 3
found 6: count 5
found 7: count 6
found 8: count 4
found 9: count 5
中间不显示了
..........................
found 90: count 4
found 91: count 5
found 92: count 6
found 93: count 3
found 94: count 5
found 95: count 6
found 96: count 4
found 97: count 6
found 98: count 5
found 99: count 6
max =6
请按任意键继续. . .
嘿嘿，不难看出一头一尾元素用二分法居然需要5-6次循环，有什么改进办法？其实研究过快速排序的三分中值摸查模块，结合二分查找法的代码，不难看出，每次二分的时候，都有三个引索值，low, mid, high，只需要对这三个索引值在数组的位置，再进行判断一次就可以减少循环次数，改进代码如下：
int bfind(int A[], int N, int x)
{
int low = 0, mid, high = N-1;
while(low <= high)
{
mid = (low + high) >> 1;
if(A[mid] == x) return mid;
if(A[low] == x) return low;//添加
if(A[high] == x) return high;//添加
if(A[mid] < x){
--high;//添加
low = mid +1;
}
else{
++low;//添加
high = mid -1;
}
++count;
}
return -1;
}
只添加了四行代码，再来看看为数组为10效果：
found 0: count 0
found 1: count 1
found 2: count 1
found 3: count 1
found 4: count 0
found 5: count 1
found 6: count 1
found 7: count 2
found 8: count 1
found 9: count 0
max =2
请按任意键继续. . .
不仅是查找次数少了，而且各元素找到所用的次数也减少了，为100的情况就不重复帖了，感兴趣的自行验证。
总结，代码在思考中进化，玩程序有趣的地方。