一个关于二分法查找的实现，这里不明白

zwz_1984

代码原型如下：
#include <stdio.h>

#include <stdlib.h>


#define NELEMS(arr) (sizeof(arr) / sizeof(arr[0]))



int numarray[] = {123, 145, 512,332,343,545,33, 627, 800, 933};



int numeric (const int *p1, const int *p2)

{

return(*p1 - *p2);

}



int lookup(int key)

{

int *itemptr;



/* The cast of (int(*)(const void *,const void*))

is needed to avoid a type mismatch error at

compile time */

itemptr = bsearch (&key, numarray, NELEMS(numarray),

sizeof(int), (int(*)(const void *,const void *))numeric);

return (itemptr != NULL);

}



int main(void)

{



if (lookup(512))

printf("512 is in the table.\n");

else

printf("512 isn't in the table.\n");



return 0;

}


bsearch 的实现如下
void * __cdecl bsearch (
        REG4 const void *key,
        const void *base,
        size_t num,
        size_t width,
        int (__cdecl *compare)(const void *, const void *)
        )
{
        REG1 char *lo = (char *)base;
        REG2 char *hi = (char *)base + (num - 1) * width;
        REG3 char *mid;
        unsigned int half;
        int result;

        while (lo <= hi)
                if (half = num / 2)
                {
                        mid = lo + (num & 1 ? half : (half - 1)) * width;
                        if (!(result = (*compare)(key,mid)))  
                                return(mid);
                        else if (result < 0)
                        {
                                hi = mid - width;
                                num = num & 1 ? half : half-1;
                        }
                        else    {
                                lo = mid + width;
                                num = half;
                        }
                }
                else if (num)
                        return((*compare)(key,lo) ? NULL : lo);
                else
                        break;

        return(NULL);
}


在函数指针中 (*compare)(key,mid)，我对key,mid解引用，得不到正确的值
可是为什么在int numeric (const int *p1, const int *p2)  中我对p1和P2进行解引用，就可以得到正确的值，这里我很不理解。求知道的朋友帮忙

zwz_1984

追加，数组应该是排好序的int numarray[] = {123, 145, 512,534,555,576,600, 627, 800, 933}; 这个值是对的

zwz_1984

自己解决了，是我自己理解错误了，这里应该用指针的强制转化(int *)key 和(int *)mid

笨笨熊

二分查找本来就是需要有序的，乱序的，二分查找失效！你出现找不到512，很正常！

笨笨熊

“在函数指针中 (*compare)(key,mid)，我对key,mid解引用，得不到正确的值
可是为什么在int numeric (const int *p1, const int *p2)  中我对p1和P2进行解引用，就可以得到正确的值”，问题一：函数指针compare有两个形参，形参是指针类型，你调用的时候，要类型匹配；问题二：函数指针的实现中，做的功能是比较指针存储的内容的数据的大小，解引用取指针中数据进行比较。

小号4

路过，支持一下楼主

zZ_小春

想问下楼主强化指针是什么意思呢:lol: