Thread: Binary searches

A binary search operates on a presorted container. For instance suppose we have an array of 20 elements containing in order 1-20.

if we were going to do a binary search on this for number x we do this.....

check middle number in array (middle element)
is it x?
if yes stop!
is x bigger or smaller than middle number.
if smaller array size is halved and we rinse/repeat on lower half of array
if bigger array size is halved and we rinse/repeat on upper half of array.

because the array is sorted you can immediately discount half of it with just one comparison.

so back to our example..... 1-20 in order in an array. lets look for number 17

check array[10]
find 11.... looking for 17. we now know that 17 does not occur before array[10]
check array[15]
find 16. we now know that 17 does not occur before array[15]
check array [17]
find 18. we know know that 17 does not occur after array[17]
check array [16]
find 17 stop. found in 4 comparisons else report 17 not found in array.

im sure you get the picture. Because the problem can be seen as a smaller sub-set of the original problem you can use recursion to model this nicely.

now you have a go at writing a recursive binary search function.Post what you do and we will help you fix it if need be.

First and foremost, only use a binary search when you have a sorted array that obviously contains at least one element.

In a binary search, you will always start in the middle. To determine the middle of the array you must know where the array begins and ends. Since arrays are zero-based in C/C++, an array of 30 elements will begin at element 0 and end at element 29. To find the middle, simply add the first element to the last element and divide the result by two:

middle = (first_element + last_element) / 2

When performing this type of calculation, middle will always be an integer so that the result is truncated.

Say you are looking for the integer value 29 in a sorted array of 30 elements. First start off by finding the middle of the sorted array:

middle = (0 + 29) / 2 = 29 / 2 = 14

OK, so we start at position 14. Check to see if the value searched for (29) is greater or less than the value contained at array element 14.

Let's say that the value for element 14 is 21. The value we are looking for is greater than 21. The next step will then be to search for the middle element between our current middle (14) and our last element (29). We know that our middle is not equal to the value searched for, so we will use the position after our current middle (14 + 1 = 15) as our first element.

middle = (15 + 29) / 2 = 44 / 2 = 22

OK. We now have a new middle element to check our value against. Suppose the value at element 22 is 34. We went too high. The value searched for (29) is obviously less than 34. In this case, we will look to the left for our new middle. Our current first element will remain the first element and the element left of our current middle will now become our last element (22 - 1 = 21).

middle = (15 + 21) / 2 = 36 / 2 = 18

Our new middle is 18.

And so on until the value searched for is either found or the it is not. In the case where it is not, the first element will become larger than the last element in the range searched. This condition must be checked for to identify that the search is complete. For example:

middle = (0 + 5) / 2 = 5 / 2 = 2
middle = (3 + 5) / 2 = 8 / 2 = 4
middle = (3 + 4) / 2 = 7 / 2 = 3
middle = (3 + 2) / 3 = 5 / 2 = 2 // here is the problem

Our first (3) is now greater than our last (2). This condition needs to be checked for in every iteration.

Now that this has been discussed in some detail, here is an example binary search function:

Code:

int binarySearch(int sortedList[],
                 int listSize,
                 int target,
                 int &location)
{
    int first = 0;
    int last = (listSize - 1);
    int mid;

    while (first <= last) // check for first and last crossing
    {
        mid = (first + last) / 2;
        if (target > sortedList[mid])
        {
            // look in the upper half
            first = mid + 1;
        } // end if
        else if (target < sortedList[mid])
        {
            // look in the lower half
            last = mid - 1;
        } // end else if
        else
        {
            // found a match, exit the loop
            break;
        } // end else
    } // end while
    
    if (target == sortedList[mid])
    {
        // match was found; set location; return true (non-zero)
        location = mid;
        return 1;
    } // end if
    else
    {
        // no match; return false (0); do not set location
        return 0;
    } // end else
} // end binarySearch

David

***edit***
Sorry StonedCoder. You finished your post before mine.

Originally posted by Prezo
... could someone please email at dropkick78@hotmail.com, the basic code, or just explain it on this cheers

Most people won't respond to your email address. It goes against the _spirit_ of the forum. If you're a registered user, you can get email notifications when someone replies to a thread, if that's what you want.