CODEWITHSUNDEEP
c++functionbinary-search
Liam
Liam

Reputation: 429

Binary Search algorithm c++

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 :

  1. 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).
  2. If array[guess] equals target, then stop. You found it! Return guess.
  3. If the guess was too low, that is, array[guess] < target, then set min = guess + 1.
  4. Otherwise, the guess was too high. Set max = guess - 1.
  5. Go back to step 2.

Upvotes: 0

Views: 1515

Answers (2)

Uriel
Uriel

Reputation: 16224

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.

Upvotes: 1

R Sahu
R Sahu

Reputation: 206727

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

Upvotes: 2

Related Questions