Chinaunix首页 | 论坛 | 博客
  • 博客访问: 410272
  • 博文数量: 155
  • 博客积分: 2590
  • 博客等级: 少校
  • 技术积分: 2161
  • 用 户 组: 普通用户
  • 注册时间: 2012-10-25 09:33
文章分类

全部博文(155)

文章存档

2015年(1)

2014年(2)

2013年(55)

2012年(97)

分类: C/C++

2012-11-07 13:51:35

只是作为 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   
using namespace std;    
#define INVALID_INDEX -10    
int IntCompare(const int& a, const int& b, void* param)  
{  
    return a - b;  
}    
template  
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 //使用模板  
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; 后面的递归就会出问题了
原文:
阅读(760) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~