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!

Searching

Activities:

Implement the binary search function pseudocode outlined below.
Test the function using arrays of integers that are properly sorted.
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

Report abuse