达内LOGO和北京达内网址达内科技培训项目:Java培训 3G培训 Android培训 软件测试培训北京达内服务电话
C++培训
二分查找的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; 后面的递归就会出问题了