Is "Seperate" Spelled Correctly?
TG and solutions need to be checked. MF, 12/19/18
On this page, you will use a binary search algorithm to search efficiently in a sorted list.
Answering this question is simple in Snap! because you can just ask a dictionary: . But "simple" doesn't mean fast. The contains
block still has to look at each item in the list until it finds the one you are looking for (and says true
) or reaches the end of the list (and says false
). It is still a linear search.
When you are only looking for one thing in a list (for example, checking whether a particular word is spelled correctly) rather than finding all the words with some characteristic (for example, looking for all fiveletter words), you can use the strategy from Page 1: Guess My Number to make your algorithm faster. The best strategy for that problem is a binary search algorithm: always guess the middle value and then adjust your guess based on whether it was too high or too low. That way, you eliminate half the possibilities with each guess. We can use a similar strategy to look for a word in a word list.
You could have written a simpler number guessing program: the computer could guess the number 1, then 2, then 3, and so on until it finds the number. That would be a linear search algorithm; it's easier to code, but it takes longer to run because every time it makes a wrong guess, it eliminates only that guess. With binary search, every wrong guess eliminates half the possibilities at once.
:
Binary Search
AAP2.P.1, AAP2.P.2
A binary search algorithm starts in the middle of a sorted list and repeatedly eliminates half the list until either the desired value is found or all elements have been eliminated.
AAP2.O.1
Linear search does a complete traversal of the list. Binary search saves time by doing a partial traversal of the list.
The one thing that almost everyone knows about computers is that they use binary: ones and zeros. Binary search has nothing to do with that. The word "binary" just means "two," whether it's two digits or two halves.

Compare this
binary search
block with your code from Page 1: Guess My Number. What parts are the same? What parts are different?
The
>
block (as well as the
<
and
=
blocks) compares words alphabetically:
 Check whether "seperate" is spelled correctly by using
binary search
to look for the word in the sorted list .
 Try
binary search
with some words that you know are spelled correctly and some that you know are incorrect.
Maybe change it to "Practice using binary search
: Try it with some words that you know are spelled correctly and some that you know are incorrect." MF, 7/13/20
 Now use
binary search
to search for the same words in the unsorted 100,000 words.
AAP2.P.2
 Why does binary searching work on one list but not the other? Consider how the binary search algorithm works.
The contains
block can't make any assumptions about the ordering in list you are searching, but if you are looking for one thing in a sorted, list you can use binary search.
AAP2.P.2
Two things affect whether you can use a binary search algorithm to make your program more efficient:
 What question you are trying to answer? Are you searching for one thing in a list or are you finding all the things in the list with some characteristic?
 What is the condition of your data? Are they sorted or unsorted?

find one value 
find many values 
sorted data 
can use binary search 
must use linear search 
unsorted data 
must use linear search 
must use linear search 
If you are working with short lists, it's not so important which algorithm you use. It's when you are dealing with a lot of data that you have to think carefully about the algorithm.

AAP2.P part b, AAP2.P.2
In order to use a binary search, the data must be...
binary
All data in a computer are represented using binary (ones and zeros), but that has nothing to do with binary searches, which compare against the middle value to choose which of two halves to eliminate.
sorted
Correct! If the data are sorted, then comparing to the middle value will give you good information about which half of the data to keep.
unsorted
If the data are unsorted, you can't be sure that everything before or everything after the middle value can be eliminated.
linear
"Linear" is the name of another search algorithm, not a property of the data.
Which of the following questions can be answered with a binary search, assuming the data are sorted? Check all that apply:
What is my friend Rasheed's phone number?
Correct! You are searching for one phone number in the list.
Give me a list of all the Beyoncé songs.
We have to find all the Beyoncé songs, not just one.
Tell me if bread is on my shopping list.
Correct! You are searching for one item in the list.
Who in my contact list lives on Grand Avenue?
Your contact list is probably sorted by name, not by address. Also, there may be more than one person who lives on Grand Avenue.
 Build a spellchecker.
Use
to convert the input text into a list.
 Should your spellchecker look through the dictionary for each word of the text or look through the text for each word of the dictionary?