0

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.

FlashSonic526
  • 101
  • 6
  • 12
  • 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. – FlashSonic526 Nov 26 '19 at 16:16
  • Does your prof want you to use some other type of data structure? Like a map or a set? – GenericDeveloperProfile Nov 26 '19 at 16:20
  • 2
    So what is the problem – Tyler Nov 26 '19 at 16:21
  • 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 Nov 26 '19 at 16:22
  • Case insensitive compare: [did you mean this](https://stackoverflow.com/questions/11635/case-insensitive-string-comparison-in-c)? 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. – Rup Nov 26 '19 at 16:25
  • @Tyler I am so sorry for the confusing, there're two problems that I want to ask, the first one will be "How to do binary search without arrays?", and the second one will be how to use .equalsIgnoreCase without creating another function (block of code). – FlashSonic526 Nov 26 '19 at 16:29
  • If you're just guessing a number, there's no need for any arrays, no. If it's somewhere between 1 and 1000, guess 500, if it's bigger, guess 750, if it's less, 250, and so on in a normal binary search pattern. – Shawn Nov 26 '19 at 16:29
  • @Blondie I guess no, just write a program that can perform a binary search without array. – FlashSonic526 Nov 26 '19 at 16:30
  • @Tyler try running it, the program cannot guess the number that is provided by the user, it will go for a pattern. – FlashSonic526 Nov 26 '19 at 16:31
  • In that case your post should provide what is wrong with the code, to help us help you. What do you input, what output do you get, and what output do you expect – Tyler Nov 26 '19 at 16:32
  • @Tyler 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. – FlashSonic526 Nov 26 '19 at 16:33
  • @Rup I think yes, but it imports something like this and makes me confusing, I asked somebody before and he told me that the only two things that I have to do are import , then use strcasecmp() and it should work. I tried it at home and it gave me an error, I asked before but someone deleted my post.... Please help! – FlashSonic526 Nov 26 '19 at 16:40

3 Answers3

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.

Tyler
  • 955
  • 9
  • 20
  • 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. – FlashSonic526 Nov 26 '19 at 16:46
  • So in this case, should I add another if statement after the first if statement in the while loop in the first function? – FlashSonic526 Nov 26 '19 at 16:47
1

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.

nathanesau
  • 1,681
  • 16
  • 27
  • 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. – FlashSonic526 Nov 26 '19 at 16:44
  • For 753 as the input, will it be the highest range? And for the 1 will be the lowest range? – FlashSonic526 Nov 26 '19 at 16:51
  • ``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 Nov 26 '19 at 19:47
  • 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 Nov 26 '19 at 19:49
  • 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. – nathanesau Nov 26 '19 at 19:53
1

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.

JMRC
  • 1,473
  • 1
  • 17
  • 36