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.

• sonik: I also wonder is there any way to do case-insensitivity such as .equalsIgnoreCase in java, I saw something similar online but doesn't understand what does it talking about.
• GenericDeveloperProfile: Does your prof want you to use some other type of data structure? Like a map or a set?
• Tyler: So what is the problem
• Rup: It's simulating a binary search rather than doing anything useful: I guess the idea for you to see the steps along the way? If that's the intention then it seems reasonable to me. But you'd have to ask your teacher what they expected / meant.
• Rup: Case insensitive compare: did you mean this? There are a lot of corner cases involving character encoding there, but if you just want to match upper and lower case latin characters then the simple answers work fine.

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.

• sonik: Sorry for my lack of experience which causes your trouble, I read multiple documents about binary searches, I know how it works behind the code, but I do not know how to code it, would you kindly mind teaching me? Thank you.
• sonik: So in this case, should I add another if statement after the first if statement in the while loop in the first function?

Answer 2

It seems you have already provided your attempt at performing a binary search. The number you are searching for is x.

For the answer, I am assuming you are looking for someone to review/ improve your code. Here is a simple way you can code the binary search:

#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 :)
}

Edit

You can put a cin input inside the while loop to ask user if they want to continue between iterations.

• sonik: I appreciate your help, but I do not understand what's going on, I wonder for "lower_bound" does it means the lowest number? Same as upper_bound? for "L" what does it mean? Same as r. Can you use lower_bound instead of creating new variables? Thanks.
• sonik: For 753 as the input, will it be the highest range? And for the 1 will be the lowest range?
• nathanesau: lower_bound and upper_bound are used to specify the range we are searching between. In my example, we are searching for the number 753 within the range (1, 1000). These are the lower_bound and upper_bound.
• nathanesau: We could replace l with lower_bound everywhere. However, modifying parameters passed to functions is not a good practice. It is better to declare local variables within the function.
• nathanesau: The way binary search works is to have a left (l) and right (r) boundary and to keep taking the midpoint (mid). If our midpoint is greater than the value we are searching for, we should decrease our right boundary. Otherwise, we should increase our left boundary.

Answer 3

I rewrote the function a little

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

The low and high are now being updated in the loop, otherwise you're constantly running the same comparison

AND IMPORTANT: add 1 to the high because if you enter 1000, after a certain time low will be 999 and high 1000. Search will than be 999.5 which is truncated to 999. So you'll never reach the 1000.