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:
- 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