Search algorithms are an important area of study in computer science. Just think of how often you search for information on the Internet using Google or some other search engine. It’s remarkable how much information Google’s algorithms search through and how fast they deliver the results.
As the video above describes, when you do a Google search, you aren’t actually searching the Web, you’re searching Google’s index of the Web. Google’s spider programs are constantly traversing the web, collecting millions of web pages and organizing them into an index. When you do a Web search Google’s algorithms are searching that index.
What’s the best algorithm for searching an index? An index is an ordered collection. Think of the index that comes at the back of a textbook. It is organized in alphabetical order. Each entry in the index refers to some page in the book.
To help you think about the problem of searching an index we’re going to play a guessing game. The objective of the game is to come up with the most efficient algorithm for guessing a number between 1 and 100, where most efficient means that it takes the fewest number of guesses.
One way to look at this game is that we are searching for a number in a list of numbers. Our search made use of the fact that numbers are ordered. The feedback we received - "too high" or "too low" - was based on that order. If you’re still working on figuring out an efficient algorithm, maybe the following widget will give you some ideas. Try to observe the algorithm that the widget is using. (open in a new window)
Define a pseudocode algorithm that will efficiently play the guessing game. (Remember that pseudocode is a way of describing an algorithm wihtout using a specific programming language. Your pseudocode should be clear enough that someone else could implement it in a programming language of their choice.)
There is an efficient algorithm for the guessing game problem, known as the binary search algorithm. It is called binary search because you repeatedly divide the search space into two and eliminate one half of the search space.
The algorithm must have the clause "until you run out of numbers in the list" because the target number may not be in the list. If you run out of numbers, then the target number is not in the list.
For a list of 16 items, you need a maximum of 5 guesses to find the secret number, because \(2^5\) > 16. For a list of 64 numbers you need a maximum of 7 guesses, since \(2^7\) > 64. For a list of 50 numbers, you need a maximum of 6 guesses, since \(2^6\) > 50.
To find the maximum number of guesses needed to find a number in a nonempty list of N items, you need to find the smallest integer k such that \(2^k\) > N. The maximum number of guesses is k.
Do you need a calculator to figure that out? Not really. Here’s an easy way to figure out that maximum number of guesses for any value of N. Just write down the powers of 2 in a table like this:
So, when N = 100, find the first number in the right column that’s greater than 100 and the number in the left column will tell you how many guesses you need.
100 is the worst-case number of guesses when you guess each number in order.
50
50 is the average number of steps when you guess each number in order.
7
\(2^7 = 128\text{,}\) so 7 guesses can search at most 127 numbers. This is enough to search a range of 100 numbers.
6
\(2^6 = 64\text{,}\) so 6 guesses can search at most 63 numbers. Because 100 is greater than 63, 6 guesses are not always enough for the worst-case scenario.
\(2^8 = 256\text{,}\) so 8 guesses can search at most 255 items. With 500 items, 8 guesses are not enough to guarantee finding the target.
9
\(2^9 = 512\text{,}\) which is greater than 500. Binary search works by dividing the search interval in half with every single guess. The worst-case scenario requires finding the minimum number of steps (k) such that \(2^k\) > N, where N is the size of the range (500).
250
This represents the average number of guesses for a linear search (sequential search), where items are checked one by one from beginning to end (N / 2).
500
This represents the maximum (worst-case) number of guesses for a linear search, where the target number happens to be the last number checked (N).
The binary search algorithm is very fast, but the data has to be sorted (already in order). What if you had to search a set of data that was not sorted? Binary search won’t work in that case. To illustrate this problem, let’s try a variation of our guessing game. This time the app will only tell you if your guess is right or wrong, not whether it is too high or too low. Try it. (Open widget in new window.)
As you can see from this game, if you don’t know the order of the items you are going to search, you have no choice but to search them sequentially if you definitely want to find the secret number.
Subsection3.16.4Comparing Linear vs. Binary Search Algorithms
Here is a comparison of linear (sequential) search and binary search looking for a target in a list of N items in AP style pseudocode. Don’t worry about understanding the details about the binary search algorithm, but do understand the general way it works. Binary search is more complex but it is much faster. However, the list must be in a sorted order for a binary search to work. Linear search is slower but works with any list in any order.
FOR EACH item in List
{
IF (item = target)
DISPLAY "Found target!"
}
low ← 0
high ← N
# compute the middle of the list, rounded down
middle ← (low + high) / 2
REPEAT UNTIL (item[middle] = target OR low > high)
{
IF (target < item[middle])
# This cuts off the top half of the list
high ← middle - 1
IF (target > item[middle])
# This cuts off the bottom half of the list
low ← middle + 1
# This computes new middle of the list, rounded down
middle ← (low + high) / 2
}
IF (item[middle] = target)
DISPLAY "Found target!"
ELSE
DISPLAY "Target not in list"
In this section, we have learned about two different search algorithms: linear (sequential) search and binary search. Linear search is simpler to implement but slower, while binary search is more complex but much faster, provided the data is sorted.
Review the vocabulary in this lesson. Drag the vocabulary term from the left and drop it on its correct definition on the right. Click the "Check Me" button to see if you are correct.
Looking up a person’s name in the phone book given the person’s phone number.
Let me add new information to help you solve this question. A phone book is arranged in order, but it is in order by last name . In order to solve this problem using a binary search, the phone book would need to be in order by phone number.
Looking up a word in a Webster’s dictionary.
True. A dictionary is arranged in order alphabetically. Thus, a binary search can be used to find any word in a dictionary.
Looking up a phone number in the phone book given the person’s full (unique) name.
True. A phone book is arranged in order by last name. If you know the person’s full name this includes their last name and you can then perform a binary search to find their phone number.
Finding the smallest number in a list of numbers arranged randomly.
Let me add new information to help you solve this. A binary search is only appropriate when the collection you are searching is arranged in order .
Arranging a deck of cards from the lowest to the highest value cards.
Let me add new information to help you solve this question. When you arrange items or objects you are sorting through them. Therefore, a search algorithm is not appropriate for this problem.
Looking up a person’s name in the phone book given the person’s phone number.
True. A phone book is arranged in order by last name, not by phone number. Therefore, you would need to start at one end of the phone book and check each phone number individually, in order, until you find the phone number you were given and then you can find the last name associated with the phone number.
Looking up a word in a Webster’s dictionary.
True. A linear search can be used to look up a word in the dictionary. However, a linear search would not be the most efficient search algorithm to use. Since a dictionary is in alphabetical order, you could solve this problem more efficiently using a binary search.
Looking up a phone number in the phone book given the person’s full (unique) name.
True. A linear search can be used to look up someone’s phone number in the phone book. However, a sequential search would not be the most efficient search algorithm to use. Since the phone book is arranged in order by last name, you could solve this problem more efficiently using a binary search.
Guessing a secret number between 1 and 100.
True. A linear search can be used to guess a secret number between 1 and 100. However, a linear search would not be the most efficient search algorithm to use. Since the numbers 1 to 100 are ordered numerically, you could solve this problem more efficiently using a binary search.
Arranging a deck of cards from the lowest to the highest value cards.
When you arrange a collection you are sorting. Therefore, a search algorithm cannot be used to solve this problem.
A sorted list of numbers contains 500 elements. Which of the following is closest to the maximum number of list elements that will be examined when performing a binary search for a value in the list?
