How to do binary search without arrays? c++

Question

I wrote a program which it should be able to do perform a binary search from 1-1000, the question gave by the teacher wants us to do it without array such as int array[] = {1, 2, 3, 4, 5....};, instead, he wants us to do it like let the user pick a number then use binary search. ps. I am new to c++ and I am still learning procedure programming.

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

For example, if you enter 150, the outcome will continuously give the outcome of 571, 286, 143, 571, 286 until you ask it to stop. Different inputs will have different outcomes, but they will keep giving 3 or 4 the same number and keep looping it.

Answer 1

You need to update your bounds each loop. High and low. If x is greater than search, you should never go lower than search. set low to search. Same thing with if x < search, search should be the new high. Then calculate search again. You should read up on some example binary searches

Your code should look like this

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

Each "search" you eliminate half of the remaining possible values. If the number is 750, and you start with 500, you know because 750 > 500, it is not 0-500. So the new low is 501. That is now the lowest possible value for x.