如何在C中简化此有效的二进制搜索代码？ [英] How can I simplify this working Binary Search code in C?

问题描述

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

Hey guys started programming in C few weeks ago learning about algothiritms, just wondering how would you make my code more simple its just a binary search function. But the only thing is you must keep the arguments the same, thanks in advance.

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的情况，确保测试的位置始终有效，确保没有溢出（即，（（low + high）/ 2'不是最好的书写方式），请确保新的测试位置始终与前一个不同，依此类推。

There are a bunch of little things you have to get right in a binary search: handle the length=0 case, make sure the position you test is always valid, make sure you don't overflow (i.e., `(low+high)/2' is not the best way to write that), make sure the new test position is always different from the previous one, etc.

次，我写的每个二进制搜索现在都是这样完成的：

After having done it like a million times, every binary search I write is now done just like this:

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。我们无需在循环内进行相等性测试，而是可靠地找到要查找的元素所属的位置，每次迭代仅使用一次比较，然后在最终测试中查看所需元素是否为

Notice that we only need to do one comparison per iteration, which is faster than most implementations that can do 2. Instead of doing the equality test inside the loop, we reliably find the position where the element to find belongs, using only one comparison per iteration, and then at the end test to see if the element we want is there.

我们计算 testpos 的方式可确保 pos< = testpos<限制，即使长度是最大可能的整数值，它也可以工作。

The way we calculate testpos ensures that pos <= testpos < limit, AND it works even if length is the largest possible integer value.

这种形式也很容易读取您的不变量希望看到，而不必考虑像 high< low 这样的奇怪边界条件。当您退出循环时，请 pos == limit ，这样您就不必担心使用错误的了，等等。

This form also makes it very easy to read off the invariants you want to see, without having to think about strange boundary conditions like high<low. When you come out of the loop, pos==limit so you don't have to worry about using the wrong one, etc.

此循环中的条件也很容易适应不同用途的二进制搜索，例如找到插入x的位置，确保它遍历数组中已经存在的所有xs，找到数组中的第一个 x，在数组中找到最后一个 x，等等。

The condition in this loop is also easily adaptable to different-purpose binary searches like "find where to insert x, ensuring that it goes after all the xs that are already in the array", "find the first x in the array", "find the last x in the array", etc.

这篇关于如何在C中简化此有效的二进制搜索代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！