二进制搜索不适用于 n = 1、2

Question

这是我的二进制搜索代码，n = no of elements in array

// Binary Search
// BUG: not working for n = 2

#include <iostream>

int main() {

    const int n = 1;
    int newlist[n];

    std::cout << "Enter " << n;
    std::cout << " elements in increasing order:\n";

    for( int i = 0; i < n; ++i ) {
        std::cin >> newlist[i];
    }

    int pos = 0, num;
    std::cout << "Enter number:\n";
    std::cin >> num;
    std::cout << '\n';


    int imin = 0, imax = n-1;
    int imid = (n - 1)/2;

    for( int i = 0; i < n; ++i ) {

        imid = (imin + imax) / 2;

        if( newlist[imid] == num ) {
            pos = imid;
        }

        else if( newlist[imid] < num ) {
            imin = imid+1;
        }

        else {
            imax = imid-1;
        }
    }

    if( pos != 0 ) {
        std::cout << "Found at " << pos+1;
    }

    else {
        std::cout << "Not found!\n";
    }

    return 0;
}

它确实适用于 n > 2，但无法为 n <= 2 提供正确的输出，即即使对于找到的元素也提供 Not found! 输出。

我认为一种方法是为 n <= 2 单独实现，但这会变得很麻烦！请帮忙。

Answer 1

将您的 pos 运算符设置为 -1 而不是 0。0 表示您的第一个索引，并且由于您输出未找到 pos == 0 条件下的元素，因此您的代码失败了。您应该最初将 pos 设置为 -1 并检查自身是否存在未找到的情况，如果在 pos = 0 处找到元素，则表示该元素存在于第一个索引处。

Answer 2

第一个pos等于0是正确的值。所以一开始就把pos设置成-1，然后在检查是否找到的时候和-1（或者更常见的是>= 0）比较。

其次，有几项应该更改，因为现在还没有那么多二分查找：

没有理由在循环之前初始化mid，它只是循环块中范围的临时变量。
退出搜索的条件是min > max，你不需要任何额外的计数器，因为它会运行循环总是n次，即使值没有'不存在。所以改为 while (min <= max) { ...
最后但同样重要的是，一旦找到该项目，请立即通过 break 语句退出循环。

Answer 3

我认为 for 循环不是这里要使用的控制结构，因为您想在找到正确的项目或 imin 和 imax 不合理时结束。

在给定的实现中，您甚至在找到项目后都没有停止循环，只是确认找到的项目 "n-(number of iterations until item was found)" 次。

此外，对于基于 0 的 C++ 数组和向量，将位置 == 0 作为 "not found" 的标记不是一个好主意；您可以改用 http://en.cppreference.com/w/cpp/types/numeric_limits 或 n 中的项目（因为索引从 0 到 n-1）。

理论上，您可以使用指针算法使您的数组从 1 开始，我假设您没有；我不推荐它。但是，您截取的代码缺少列表的实际定义。

二进制搜索不适用于 n = 1、2

Binary search not working for n = 1, 2

c++

search

binary-search