请为我解释这个二进制搜索功能

Question

下面是 Apple 的通用二进制搜索代码。我不擅长位操作等，所以这对我来说真的很难理解。我在下面的代码中对我理解的部分进行了评论

什么是基础？这是包含值的数组吗？
如果 nremain 是数组中未分析的值的数量，为什么我们每次迭代都将其右移 1？
也请帮我理解forloop的第一行是什么。所以我的猜测是 p 指向剩余元素的中点，但我没有得到 (nremain >>1) * width 部分。什么是宽度？将 nremain 的右移乘以 1 版本与宽度相乘如何将指针设置为中点？
sign > 0 当key > p，指针需要移动到下一个元素。这是如何通过 p + width 实现的？同样，知道宽度是多少会非常有帮助。
我知道我们在每次迭代结束时从 nremain 中减去 1 以表示已经分析了一个元素，但是在这种情况下每次迭代 nremain>>=1 的意义是什么?

提前致谢！我期待收到任何人的回复。

void *apple_bsearch(const void *key, const void *base, size_t nmemb,  
               size_t width, int (*compar)(const void *, const void *)) {
    for (size_t nremain = nmemb; nremain != 0; nremain >>= 1) {
        void *p = (char *)base + (nremain >> 1) * width; // I don't get this
        // this is comparing key & where currently p is pointing
        int sign = compar(key, p); 
        if (sign == 0) { // if p and key are equal, sign is 0
            return p;
        }
        if (sign > 0) {  // when key > p, move right
            base = (char *)p + width;
            nremain--;
        }       
    }
    return NULL;
}

Answer 1

我会做出某些假设（基于我会说的知情猜测）：

nmemb是数组的成员个数
width 等于 sizeof(array[0])
base指向数组的第一个成员，即，base == array[0]
数组已排序（从小到大）

请注意，向右移位基本上是整数除法（它会丢弃余数，例如、3 >> 1 == 1）。

该函数采用以下参数：

key，指向 const void
base，指向 const void
nmemb、size_t变量
width、size_t变量
compar，（指针）指向具有两个参数的函数（指向 const void 的 2x 指针）return 是 int

使用指向 void 的指针这一事实允许函数不知道数组元素的大小（因此是通用的）。

现在让我们逐行分析。

for 循环将 nremain 初始化为 nmemb，然后循环直到 nremain != 0（或出现 return）。循环结束时它将 nremain 除以 2，将结果向下舍入（右移 1）。
p 声明为指向 void 的指针，设置在基偏移量 nremain（要考虑的数组元素数）乘以 width。因此 p 将指向数组左半部分的末尾。例如，如果数组中有 7 个元素，则在第一次迭代中 p 将指向第 4 个元素。强制转换 (char *) base 只是确保添加了正确的字节数，假设 width == sizeof(array[0])，因为 sizeof(char) == 1.
compar 然后将 p 与 key 进行比较，成功后 p 被 returned.
如果p < key则base设置为p指向的成员后的下一个成员，nremain减1。这是由于 Eric Postpischil 的解释："The prior assignment to p effectively partitions the array into three pieces: The element pointed to by p, the elements earlier than that, and the elements after that. The number of elements earlier is nremain>>1, the number exactly at p is 1, and the number after it is (nremain-1)>>1. E.g., if nremain is 12, the parts have 6, 1, and 5 elements. Subtracting 1 from nremain at that point ensures it is set correctly by the nremain >>= 1 step for the next iteration."
重申。
如果我们没有找到值并退出for循环（注意当nremain == 1在循环结束时nremain >> 1 == 0），return NULL.

也许我的某些假设是错误的，因此您需要通过更改它们来计算代码；)。希望这对您有所帮助！

请为我解释这个二进制搜索功能

please explain this binary search function for me

c

bit-manipulation

bit-shift