只是作為 stdlib 中的 bsearch 的一個拓展吧，看看聲明：
void *bsearch(const void*key, const void *base, size_t nelem, size_t width, int(*fcmp)(const void *,const *));
參數：
第一個：要查找的關鍵字。
第二個：要查找的數組。
第三個：指定數組中元素的數目。
第四個：每個元素的長度（以字符為單位）。
第五個：指向比較函數的指針。
其實，有時候在fcmp 中僅僅憑兩個參數判斷是不夠的，如果能增加拓展性，可以傳入輔助判斷變量的話，會更好。
下面是我的實現與測試代碼：
[cpp] view plaincopyprint?
#include <iostream>
using namespace std;
#define INVALID_INDEX -10
int IntCompare(const int& a, const int& b, void* param)
{
return a - b;
}
template<class T1, class T2>
int BinarySearch(const T1* theArray,
int length,
const T2& key,
int (*compare)(const T1&, const T2&, void* param),
void *param)
{
int indexRet = INVALID_INDEX;
int mid = length / 2;
int cmp = compare(theArray[mid], key, param);
if (cmp == 0)
{
indexRet = mid;
}
else if (length != 1)
{
if (cmp < 0 && length != 1)
{
//中間元素小於 key，表示元素在右邊
indexRet = BinarySearch(theArray + mid, length - mid, key, compare, param);
if (indexRet != INVALID_INDEX)
{
indexRet += mid;
}
}
else
{
indexRet = BinarySearch(theArray, mid, key, compare, param);
}
}
return indexRet;
}
int main()
{
int length = 0;
int i = 0;
int key = 0;
int index = INVALID_INDEX;
cin >> length;
int* aArray = new int[length];
for (i = 0; i < length; i++)
{
cin >> aArray[i];
}
cin >> key;
index = BinarySearch(aArray, length, key, IntCompare, NULL);
if (index == INVALID_INDEX)
{
cout << "The element is not exist." << endl;
}
else
{
cout << "The element position is " << index << "." << endl;
}
delete aArray;
return 0;
}
輸入：
10
1 2 3 4 5 6 7 8 9 10
5
輸出：
The element position is 4.
第一行是數組元素個數n，第二行是n個數組元素，最後一個是需要查找的 key
代碼說明：
template<class T1, class T2> //使用模板
int BinarySearch(const T1* theArray, //需要查找的數組
int length, //數組元素個數
const T2& key, //需要查找的 key ，類型可以不必與數組相同
int (*compare)(const T1&, const T2&, void* param), //比較函數的函數指針
void *param) //附加比較參數，將被傳入 compare 中輔助判斷
後面基本就是簡單的遞歸二分查找了，需要注意的是，當 length == 1 時，應該作為遞歸出口，即使找不到也不能再遞歸了，不然就死循環了
因為 mid = length / 2 == 1 / 2 == 0; 後面的遞歸就會出問題了
