Binary Search algorithm c++

Question

I'm trying to write a function which takes an array of integers & searches the part of the array between the first and last for the given value. If the value is in the array, return that position. If it is not, I want to return -1.

Here is the code for my function.

    int binarySearch(int *array, int min, int max, int value) {
    int guess = 0;
    bool found = false;
    while (!found) {
        guess = ((array[min] + array[max]) / 2);
        if (array[guess] == value) {
            found = true;
            return guess;
        }
        else if (array[guess] < value) {
            min = guess + 1;
        }
        else if (array[guess] > value) {
            max = guess - 1;
        }
    }
    return -1;
}

I'm unsure how to break out of the while loop when the value you are searching for is not in the array? This is the pseudocode I am following for implementing a binary search function :

Let min = 0 and max = n-1(array size -1 ). Compute guess as the average of max and min, rounded down (so that it is an integer).
If array[guess] equals target, then stop. You found it! Return guess.
If the guess was too low, that is, array[guess] < target, then set min = guess + 1.
Otherwise, the guess was too high. Set max = guess - 1.
Go back to step 2.

Recursive algorithms typically don't need a while-loop.

user2100815
– user2100815

2017-02-13 22:18:59 +00:00
Commented Feb 13, 2017 at 22:18 — user2100815
– user2100815, Commented Feb 13, 2017 at 22:18

R Sahu · Accepted Answer · 2017-02-13 23:02:02Z

I think it makes sense to change what the function returns. Instead of returning guess, it should return a valid index if the item is found and -1 otherwise.

Also, you are using guess as a value and as an index. That will definitely cause problems.

guess is a value below.

    guess = ((array[min] + array[max]) / 2);

guess is an index below.

    else if (array[guess] < value) {

Here's my suggestion:

// Return the index if found, -1 otherwise.
int binarySearch(int *array, int first, int last, int value)
{
   // Terminating condition 1.
   // If first crosses last, the item was not found.
   // Return -1.
   if ( first > last )
   {
      return -1;
   }

   int mid = (first + last)*0.5;

   // Terminating condition 2.
   // The item was found. Return the index.
   if ( array[mid] == value )
   {
      return mid;
   }

   // Recurse
   if (array[mid] < value)
   {
      return binarySearch(array, mid+1, last, value);
   }
   else
   {
      return binarySearch(array, first, mid-1, value);
   }
}

Uriel · Accepted Answer · 2017-02-14 01:20:15Z

1

No need for recursion if you use a while loop, just remember to calculate guess every time, and set guess to the middle of the indexes, not their values:

int binarySearch (int *array, int first, int last, int value)
{

    int guess = 0;

    while (first != last || array[guess] == value) {
        guess = (first + last) / 2;

        if (array[guess] == value)
            return guess;
        else if (array[guess] < value)
            last = guess + 1;
        else if (array[guess] > value)
            first = guess - 1;
    }

    return -1;
}

I would also suggest

int first = 0, last = sizeof(array) / sizeof(array[0]) - 1;

instead of passing them as arguments.

edited Feb 14, 2017 at 1:20

answered Feb 13, 2017 at 22:21

Uriel

16.3k6 gold badges29 silver badges48 bronze badges

6 Comments

Liam Over a year ago

i copy and pasted my old method by accident. My most recent method is now in the updated post

Uriel Over a year ago

@Liam this answer still stands; also, you didnt copy the whole new function

Liam Over a year ago

thanks, what is last = sizeof(array) / sizeof(array[0]) - 1 doing?

Kamil Koczurek Over a year ago

This code (last = sizeof(array) / sizeof(array[0]) - 1;) doesn't work when array is passed to function as parameter and this last will always be 0.

rlbond Over a year ago

@UrielEli As previously mentioned, sizeof(array) will not work when the array is passed as a function argument. Usually the C++ style is to pass a pointer to the front of the range and a pointer past-the-end of the range anyway

|

Collectives™ on Stack Overflow

Binary Search algorithm c++

2 Answers 2

Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related