c - Where is the mistake in my code to perform Binary Search?

Question

I was writing up code for a binary search algorithm.

Code:

#include "cs50.h"

int main(void) {
    int n = GetInt();
    int value = GetInt();
    int values[n];

    for (int i = 0; i < n; i++) {
        printf("Put in number %i ", i + 1);
        values[i] = GetInt();
    }

    int mid = (n - 1) / 2;
    int en = 0;
    int ex = n - 1;

    for (int i = 0, xt = i + 1; i < xt; i++) {
        if (value > values[mid]) {
            en = mid;
            mid = (en + ex) / 2;
        }
        else if (value < values[mid]) {
            ex = mid;
            mid = (en + ex) / 2;
        }
        else if (value == values[mid]) {
            printf("found");
            break;
        } else {
            printf("not found");
            break;
        }
    }
}

But it only works when the value to be found is somewhere in the middle.

It fails when :

1. value to be found is first or last.
2. value to be found is not in the values inputted.

I really cannot figure out the mistake.

Answer 1

There are a bunch of little things you have to get right in a binary search: handle the length=0 case, make sure the position you test is always valid, make sure you don't overflow (i.e., `(low+high)/2' is not the best way to write that), make sure the new test position is always different from the previous one, etc.

After having done it like a million times, every binary search I write is now done just like this:

bool search(int array[], int length, int valueToFind)
{
    int pos = 0;
    int limit = length;
    while(pos < limit)
    {
        int testpos = pos + ((limit - pos) >> 1);

        if (array[testpos] < valueToFind)
            pos = testpos + 1;
        else
            limit = testpos;
    }
    return (pos < length && array[pos] == valueToFind);
}

Notice that we only need to do one comparison per iteration, which is faster than the searches in the other answers. Instead of doing the equality test inside the loop, we reliably find the position where the element to find belongs, using only one comparison per iteration, and then at the end test to see if the element we want is there.

The way we calculate testpos ensures that pos <= testpos < limit, AND it works even if length is the largest possible integer value.

This form also makes it very easy to read off the invariants you want to see, without having to think about strange boundary conditions like high<low. When you come out of the loop, pos==limit so you don't have to worry about using the wrong one, etc.

The condition in this loop is also easily adaptable to different-purpose binary searches like "find where to insert x, ensuring that it goes after all the xs that are already in the array", "find the first x in the array", "find the last x in the array", etc.