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 :

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.

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

Answer 1

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

Answer 2

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.

• Liam: i copy and pasted my old method by accident. My most recent method is now in the updated post
• Uriel: @Liam this answer still stands; also, you didnt copy the whole new function
• Liam: thanks, what is last = sizeof(array) / sizeof(array[0]) - 1 doing?
• Kamil Koczurek: 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: @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