二分查找的 C++ 实现

只是作为 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; 后面的递归就会出问题了

补充：软件开发 , C++ ,