c - 如何在C中简化此有效的二进制搜索代码？

嘿，几个星期前开始用C语言学习有关algothiritms的知识，只是想知道如何通过二进制搜索功能使我的代码更简单。但是唯一的是，您必须保持相同的参数，在此先感谢。

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;
    }
}

最佳答案

在二进制搜索中，您需要做一堆小事情：处理length = 0的情况，确保测试的位置始终有效，确保没有溢出（即，（（低+高） / 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，并且即使length是最大可能的整数值，它也可以工作。

这种形式还使您很容易读取想要查看的不变量，而不必考虑像high<low这样的奇怪边界条件。当您退出循环时，请使用pos==limit，因此您不必担心使用错误的名称，等等。

此循环中的条件还可以轻松地适应不同用途的二进制搜索，例如“查找在哪里插入x，确保它在数组中已经存在的所有xs之后进行”，“在数组中找到第一个x”，“找到数组中的最后一个x”，等等。

关于c - 如何在C中简化此有效的二进制搜索代码？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39416560/