如何在没有数组的情况下进行二分查找？ C++

Question

我写了一个程序，应该可以进行1-1000的二分查找，老师的题目是要我们不用数组的，比如int array[] = {1, 2, 3, 4, 5....};，他要的是我们这样做就像让用户选择一个数字然后使用二进制搜索一样。 ps。我是c++新手，还在学习过程编程。

#include <iostream>
//binary search
using namespace std;

//set function for binary search, high = highest range, low = lowest range, x = the number given by the user.
int binarySearch(int x) {
    int high = 1000, low = 1;
    int search = (high + low) / 2;  //set search as the equation of the search
    //search = 500

    if (search == x)
        return search;

    while (search != x) {
        if(x > search) {
            search = (search + high) / 2;
        } else if (x < search) {
            search = (search + low) / 2;
        }

        cout << search << endl;
    }

    return search;
}

int main()
{
    int x;
    cout << "Enter a number to search: (1-1000) ";
    cin >> x;
    cout << binarySearch(x);

    return 0;
}

比如你输入150，结果会一直给出571、286、143、571、286的结果，直到你让它停止。不同的输入会有不同的结果，但它们会一直给 3 或 4 个相同的数字并不断循环。

Answer 1

您需要在每个循环中更新边界。高和低。如果 x 大于搜索，则永远不要低于搜索。设置低搜索。与 if x < search 相同，search 应该是新高。然后重新计算搜索。您应该阅读一些示例二进制搜索

您的代码应如下所示

int binarySearch(int x) {
    int high = 1000, low = 1;
    int search = (high + low) / 2;

    if (search == x)
        return search;

    while (search != x) {
        if(x > search) {
            low = search + 1;
            search = (low + high) / 2;
        } else if (x < search) {
            high = search - 1;
            search = (low + high) / 2;
        }

        cout << search << endl;
    }

    return search;
}

你每 "search" 消除剩余可能值的一半。如果数字是 750，而你从 500 开始，你知道因为 750 > 500，它不是 0-500。所以新的低点是 501。这是 x 的最低可能值。

Answer 2

您似乎已经提供了执行二进制搜索的尝试。您要搜索的号码是x。

对于答案，我假设您正在找人审查/改进您的代码。下面是编写二进制搜索代码的简单方法：

#include <iostream>

// prints binary search path for x
bool bin_search_path(int x, int lower_bound=1, int upper_bound=1000) {
   int l = lower_bound;
   int r = upper_bound;

   while(l <= r) {
      int mid = (l + r) / 2;
      std::cout << mid << std::endl;
      if (mid == x) return true;
      if (mid > x) { // go left
          r = mid - 1;
      } else { // go right
          l = mid + 1;
      }
   }

   return false; // not found
}

int main() {
   bin_search_path(753, 1, 1000); // 500 750 875 812 781 765 757 753
   return 0; // use https://www.onlinegdb.com/online_c++_compiler to try out :)
}

编辑

您可以在 while 循环中输入 cin 以询问用户是否要在迭代之间继续。

Answer 3

我稍微重写了函数

int binarySearch(int x) {
    int high = 1000 + 1, low = 1;
    int search = (high + low) / 2;  //set search as the equation of the search
    //search = 500

    if (search == x)
        return search;

    while (search != x) {
        if(x > search) {
            low = search;
            search = (search + high) / 2;
        } else {
            high = search;
            search = (search + low) / 2;
        }

        cout << search << endl;
    }

    return search;
}

低点和高点现在正在循环更新，否则你会一直运行相同的比较

重要提示：在最高价上加 1，因为如果您输入 1000，一段时间后最低价将是 999，最高价将是 1000。搜索结果将是 999.5，截断为 999。所以您永远达不到 1000 .

如何在没有数组的情况下进行二分查找？ C++

How to do binary search without arrays? c++

c++

binary-search