如何在 C 中简化此工作二进制搜索代码？

Question

大家好，几周前开始用 C 编程，学习算法，只是想知道如何让我的代码更简单，它只是一个二进制搜索函数。但唯一的事情是你必须保持论点相同，提前致谢。

bool search(int value, int values[], int n)
{
    int min = values[0];
    int max = values[n-1];
    int average = (min + max) / 2;

    if(average == value)
    {
        return true;
    }

    while (average > value) 
    {
        max = average - 1;
        average = (min + max) / 2;

    }

    while (average < value)
    {
        min = average + 1;
        average = (min + max) / 2;
    }

    if (max < min) 
    {
        return false;
    }
    if (average == value) {
         printf("%i\n", average);
        return true;
    }
    else
    {
        return false;
    }
}

Answer 1

在二分查找中有很多小事情你必须做对：处理 length=0 的情况，确保你测试的位置总是有效的，确保你没有溢出（即，`(low+high) /2' 不是最好的写法），确保新的测试位置总是与前一个不同，等等。

在做了一百万次之后，我写的每一个二分搜索现在都是这样完成的：

bool search(int[] array, int length, int valueToFind)
{
    int pos=0;
    int limit=length;
    while(pos<limit)
    {
        int testpos = pos+((limit-pos)>>1);

        if (array[testpos]<valueToFind)
            pos=testpos+1;
        else
            limit=testpos;
    }
    return (pos < length && array[pos]==valueToFind);
}

请注意，我们每次迭代只需要做一次比较，这比大多数可以做 2 的实现要快。而不是在循环内进行相等测试，我们可靠地找到要查找的元素所属的位置，每次只使用一次比较迭代，然后在最后测试以查看我们想要的元素是否在那里。

我们的计算方式testpos确保pos <= testpos < limit, 并且即使长度是最大可能的整数值也能工作。

这种形式还可以很容易地读出你想看到的不变量，而不必考虑像high<low. 当您跳出循环时，pos==limit因此您不必担心使用错误的等等。

这个循环中的条件也很容易适应不同目的的二进制搜索，比如“找到插入 x 的位置，确保它在数组中已经存在的所有 x 之后”，“找到数组中的第一个x”，“找到数组中的最后一个x”等。