How can I simplify this working Binary Search code in C?

Question

Hey guys started programming in C few weeks ago learning about algothiritms, just wondering how would you make my code more simple its just a binary search function. But the only thing is you must keep the arguments the same, thanks in advance.

bool search(int value, int values[], int n)
{
    int min = values[0];
    int max = values[n-1];
    int average = (min + max) / 2;

    if(average == value)
    {
        return true;
    }

    while (average > value) 
    {
        max = average - 1;
        average = (min + max) / 2;

    }

    while (average < value)
    {
        min = average + 1;
        average = (min + max) / 2;
    }

    if (max < min) 
    {
        return false;
    }
    if (average == value) {
         printf("%i\n", average);
        return true;
    }
    else
    {
        return false;
    }
}

score 4 · Answer 1 · answered Sep 09 '16 at 17:50

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 most implementations that can do 2. 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.

>> 1 is a shift right by one bit. It's the same as divide by two, rounding down to the nearest integer, but it's faster on some of the old computers I learned on. It rounds down even for negative numbers, which makes it different from integer division, so compilers can't necessarily optimize /2 into >>1... But that's not really important. pos + (limit-pos)/2 is just as good. The important part is that none of the intermediate results can overflow and give wrong result like (limit+pos)/2 can. — Matt Timmermans, Mar 30 '21 at 04:34

coder · Answer 2 · 2016-09-09T19:28:22.073

3

This is not a right implementation of binary search ,all conditions must be in one loop ,such as: Also max must be n-1 and not values[n-1] and min=0 instead of values[0] as also you should compare values[average] with value not just average variable.

 bool search(int value, int values[], int n){

    int min = 0;
    int max = n-1;
    int average ;

    while(max>=min){
        average = (min + max) / 2;
        if(values[average] == value)
        {
            return true;
        }

        if (values[average] > value) 
        {
            max = average - 1;
            average = (min + max) / 2;

        }

       if (values[average] < value)
        {
            min = average + 1;
            average = (min + max) / 2;
        }

    }

    return false;
}

edited Sep 09 '16 at 19:28

answered Sep 09 '16 at 17:14

coder

12,832
5
39
53

Wow you made it so much easier. The only other question I have is why did you decide to make it if(values[average] < value) instead of while(values[average] < value)? – Ray Skywalker Sep 09 '16 at 18:43
While won't work you need to make a loop and compare values[average] , value and change average for the next repeat of the loop until it is found or not found .I just saw that i had forgot one while loop in the main while loop above ,it was wrong it must be if statement not while,I just fixed it see the edited . – coder Sep 09 '16 at 19:27

How can I simplify this working Binary Search code in C?

2 Answers2

Linked