Searching

Introduction:

We have all had reason to find things in lists before: If you've ever looked up a phone number in your phone's contacts list, examined a transcript of your marks in school, tried to find out the price of tickets for a concert on Ticketmaster, and so on. The ability to find one specific item among other similar items is an important skill for humans, and as it turns out, for computers.

Searching:

Think about how you, as a human, search through a list to find one particular item. Some of the strategies you use may be applicable (even partially) to a computer. For example, if you are searching for someone's name in your contacts list, the first thing you probably note is that the list is sorted alphabetically by last name. If you know the last name of the person you are looking for, you can simply jump to that letter, quickly eliminating the other 25 letters.

Computers aren't quite that lucky, but they can do something similar. With a single comparison, they can cut the size of the array they are searching through in half!

Activities:

  1. Implement the binary search function pseudocode outlined below.
  2. Test the function using arrays of integers that are properly sorted.
  3. Test the function using arrays of integers that are NOT sorted. What happens?
function search(A, key)
    max = size(A)
    min = 0
    while min < max
        mid = floor(max + min)/2
        if A[mid] < key
            min = mid + 1
        else
            max = mid
        end if
    end while
    if min == max and A[min] == key
        return min
    else
        return -1
    end if
end function