我的代码中执行二进制搜索的错误在哪里？ [英] Where is the mistake in my code to perform Binary Search?

问题描述

我正在为二进制搜索算法编写代码。

I was writing up code for a binary search algorithm.

代码：

#include "cs50.h"

int main(void) {
    int n = GetInt();
    int value = GetInt();
    int values[n];

    for (int i = 0; i < n; i++) {
        printf("Put in number %i ", i + 1);
        values[i] = GetInt();
    }

    int mid = (n - 1) / 2;
    int en = 0;
    int ex = n - 1;

    for (int i = 0, xt = i + 1; i < xt; i++) {
        if (value > values[mid]) {
            en = mid;
            mid = (en + ex) / 2;
        }
        else if (value < values[mid]) {
            ex = mid;
            mid = (en + ex) / 2;
        }
        else if (value == values[mid]) {
            printf("found");
            break;
        } else {
            printf("not found");
            break;
        }
    }
}

但仅当

在以下情况下失败：

1. 要查找的值是第一个或最后一个。


2. 要查找的值不在输入的值中。

我真的无法弄清错误。

推荐答案

有很多小事情需要解决在二进制搜索中：处理length = 0的情况，确保测试的位置始终有效，确保没有溢出（即，（（低+高）/ 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);
}

请注意，我们每次迭代只需要进行一次比较，比其他答案中的搜索。我们不必在循环内进行相等性测试，而是可靠地找到要查找的元素所属的位置，每次迭代仅使用一次比较，然后在最后的测试中查看所需元素是否存在。

Notice that we only need to do one comparison per iteration, which is faster than the searches in the other answers. 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.

这篇关于我的代码中执行二进制搜索的错误在哪里？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！