Thread: Binary searches

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    6

    Thumbs up Binary searches

    Hey guys i was wondering, if someone would be able to try and explain how to do a binary search to me rather then a linear search. its been troubling me for ages!

    and i just cant get the basics for it, could someone please email at [email protected], the basic code, or just explain it on this cheers

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    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.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    Registered User Strider's Avatar
    Join Date
    Aug 2001
    Posts
    149
    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.
    Last edited by Strider; 09-10-2002 at 07:26 AM.
    One Ring to rule them all, One Ring to find them,
    One Ring to bring them all and in the darkness bind them
    In the Land of Mordor where the Shadows lie.

  4. #4
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231

    Re: Binary searches

    Originally posted by Prezo
    ... could someone please email at [email protected], 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.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  5. #5
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    Here is another example of binary seach code:

    Code:
    int binarysearch (int list[], int listLength, int searchItem)
    {
        int first = 0;
        int last = listlength - 1;
        int mid;
    
        bool found = false;
    
        while (first <= last && !found)
        {
              mid = (first + last) /2;
    
              if (list[mid] == searchItem)
                found = true;
              else
                 if (list[mid] > searchItem)
                   last = mid - 1;
                 else
                    first = mid - 1;
       }
       if (found) 
         return mid;
       else
         return -1;
    
    }
    A nice n log n search when a list is sorted!!!

    Mr. C.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 04-02-2006, 09:31 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. binary searches
    By Viny in forum C Programming
    Replies: 4
    Last Post: 12-06-2001, 06:40 PM