首页 > 试题广场 >

二分查找是常用的编程方法，请用完整代码实现该函数。

[问答题]

二分查找是常用的编程方法，请用完整代码实现该函数（不许调用库函数）
void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));

推荐

牛客105300号

二分查找完整代码：

#include<iostream>

using namespace std;

void * bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *)){
    void *mid = NULL;
    int sign;
    while (nel > 0) {

        mid = (char *)base + width*(nel/2);
        sign = cmp(key, mid);
        if (sign == 0) return mid;//找到
        if (nel == 1) break;
        else if (sign < 0)
            nel /= 2;//下取整
        else {
            base = mid;
            nel -= nel/2;//上取整
        }

    }
    return NULL;
}

int compare(const void *val1, const void *val2) {
int iVal1 = *(int*)val1;
int iVal2 = *(int*)val2;
if (iVal1 > iVal2) {
return 1;
}
else if (iVal1 == iVal2) {
return 0;
}
return -1;
}

测试用例：

int main(){

int a[10]={1, 2, 5, 8, 10, 11,12,13,14,15};
int key = 5;

    void* res = bsearch(&key, a, 10, sizeof(int), compare);
if(res != NULL){
    cout << "索引位置：" << (int *)res - a;
}
return 0;
}

编辑于 2016-02-26 12:53:22 回复(3)

gallup

二分查找完整代码：

#include<iostream>

发表于 2015-11-02 10:35:01 回复(1)

指上弹兵赵小括

key是指向查找关键字

base指向查找的数组

那么nel是什么，是nElement的缩写吗，指的是元素个数吗

width指的是什么？是数组中的元素的个数吗？还是元素所占的类型的大小？还是什么？

傻傻分不清！

估计nel是元素个数，而width是每个元素所占的字节数；

发表于 2015-09-09 11:30:48 回复(0)

kevin_song

我没有用到Width, 请问Width该如何使用？我假设是int型数据。我的答案（完整程序）如下，请帮忙提修改意见，我好后面修改。谢谢！

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

// BinarySearch.cpp : Defines the entry point for the console application

#include "stdafx.h"
#include <iostream>

using namespace std;

//compare function
int compare(const void *val1, const void *val2)
{
    int iVal1 = *(int*)val1;
    int iVal2 = *(int*)val2;

    cout << "Compare: " << iVal1 << ", " << iVal2 << endl;

    if (iVal1 > iVal2)
    {
        return 1;
    }
    else if (iVal1 == iVal2)
    {
        return 0;
    }
    else
    {
        return -1;
    }
}

//nel: num of element, width: every element size
void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar)(const void*, const void *))
{
    int pos = nel / 2;
    cout << "Position: " << pos << endl;

    int result = (*compar)(key, (int *)base + pos);

    if (pos == 0)
    {
        return result == 0 ? (void *)base : NULL;
    }

    if (result > 0)
    {
        return bsearch(key, (int *)base + pos + 1, pos, width, compar);
    }
    else if (result == 0)
    {
        return (void *)base;
    }   
    else
    {
        return bsearch(key, base, pos, width, compar);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int array[] = { 1, 3, 5, 6, 11, 13, 17, 29, 44, 66, 79, 99, 111 };
    int arrayNum = sizeof(array) / sizeof(*array);   
    cout << "Array Element Num: " << arrayNum << endl;
 
    int searchVal = 13;
    cout << "Search Value: " << searchVal << endl;

    int *result = (int *)bsearch(&searchVal, array, arrayNum, sizeof(*array), compare);
    cout << "Result: " << (result == NULL ? "Not Found" : "Found") << endl;
 
    system("pause");
    return 0;
}

发表于 2014-12-21 17:23:48 回复(0)

提交观点

问题信息

2015 百度查找大数据开发工程师

来自：百度2015大数据云计...

上传者：小小

难度：

4条回答 83收藏 15722浏览

二分查找是常用的编程方法，请用完整代码实现该函数。

问题信息

热门推荐

相关试题