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

问题描述

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

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
", 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 的位置，确保它在数组中已经存在的所有 x 之后"，找到 first 数组中的 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屋！