Binary search

[Kyle Lanmon]

I have written a binary search algorithm and it is giving me problems. It takes too long to finish running and gets killed. How do I get it to run faster or be more efficient?

int binarySearch( int list[], int size, int value )
{
    int low = 0, high = size - 1, mid, result = -1;
    bool found = false;
    
    while ( !found )
    {
        mid = (high + low) / 2;
        if ( list[mid] < value )
        {
            low = mid + 1;
        }
        else if ( list[mid] > value )
        {
            high = mid - 1;
        }
        else
        {
            result = mid;
            found = true;
        }
    }
    return result;
}

Also, what is dot product and how do I calculate it for two arrays?

[long double main]

If the element you're searching for is in the array, then your function works fine.
But note that you loop until the element is found, so if it turns out that the element isn't there in the first place, then you get an infinite loop.

Instead, you should loop while (low <= high), and if the program breaks out of that loop, then you know what you're looking for isn't there.
You can also simplify your else statement to just else return mid;.

Dot product is just the sum of the products of corresponding array elements.
So for arrays A and B, it would be A[0]*B[0] + A[1]*B[1] + ....

[Duthomhas]

You forgot to check against low >= high:

while (!found && (low < high))


The dot product is a useful operation in vector mathematics. To find the dot product, find the sum of the pairwise multiplication of the elements.

For example: { 1, 2, 3 } . { 4, 5, 6 } = 1*4 + 2*5 + 3*6 = 32

Note that the two lists of numbers must have the same length.


Hope this helps.

[Kyle Lanmon]

My prof makes us only use one return statement in our functions.

My while statement is now using (low < high) as the condition. Here is some sample output.

Testing binarySearch()......
10	21	22	36	48	56	58	76	86	95	
Found 4199216 at 10
Found 10 at 0

How do I handle a "not found" situation from inside a function?

[Script Coder]

You could try something like this:

int binarySearch( int list[], int size, int value )
{
    int low = 0, high = size - 1, mid, result = -1;
    
    while ( high>=low )//change here
    {
        mid = (high + low) / 2;
        if ( list[mid] < value )
        {
            low = mid + 1;
        }
        else if ( list[mid] > value )
        {
            high = mid - 1;
        }
        else
        {
            result = mid;
            return result; //change here
        }
    }
    return -1;//change here
}

I just took your code and edited a few places. Basically you just need to check for a positive return value.

[dhayden]

You could return -1 from the function if the value isn't found and let the caller deal with the error. Another way is to change your function to:

bool binarySearch( int list[], int size, int value, int &result)

If the value is found, return true and set result to the index. If not found, return false and don't change result. I like this better because it's harder for the caller to screw up and blindly assume that the value is found.

My prof makes us only use one return statement in our functions.

This is supposed to make the code easier to read, understand and debug. But in my 30 years of professional programming I find that you often have to twist the logic around to do it. So on balance I don't think it's worth it. Of course while you're taking your class you should do what the prof says, but afterwards....

[Duthomhas]

The only change I had to make to run the code properly was line 6:

while (!found && (low < high))

Everything else works just fine, including the flaggy code, which (if you want to be pedantic) could have been accomplished with a break instead.

When a beginner is first designing algorithms, it is clear that the results will not be as polished and sophisticated as what the more experienced of us will produce. What is important is that the beginner's code be well thought out.

OPs code is just that. OP created a loop, determined exactly when and how to terminate it, and accounted for all test cases inside the loop. The only thing was he forgot that low may cross high. Over all, it is a good piece of code, and would be compiled and executed just as efficiently as many more snazzy looking versions.