如何在不使用数组的情况下进行二进制搜索？ 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。

关于答案，我假设您正在寻找某人来审查/改进您的代码。这是您可以对二进制搜索进行编码的一种简单方法：

#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 2

我稍微重写了功能

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。

Answer 3

您需要在每个循环中更新边界。高和低。如果x大于搜索，则绝不能低于搜索。设置较低的搜索条件。如果x

您的代码应该看起来像这样

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;
}

每个“搜索”都消除了剩余的可能值的一半。如果数字是750，并且您以500开头，则知道因为750> 500，所以它不是0-500。因此新的低点是501。这是x的最低可能值。