c - 如何简化 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”等