block and used it with keep to find words of a specific length in a word list. The question here is: How long does a process like that take?On this page, you will compare the time required for binary search and for linear search.
Students will have built a block and used it with keep to find words of a specific length in a word list. The question here is: How long does a process like that take?
does () have () letters? predicate.The blank input slot in the predicate is required; this is where each item from the list goes as it is checked by the predicate.
keep block. Keep filters an input list according to the results of a predicate expression (a true/false question).
length of block that finds the number of items in a list; this is different from the green length of block that finds the number of letters in a text string.
block provided in this project to determine how long it takes for the computer to answer that question.
The computation time block takes any reporter (with its inputs filled in), computes the result but ignores it, and instead reports how long it took to do the computation (in milliseconds).
In this example, it took 27 milliseconds to compute the list of integers from 1 to 1000. (The report you see will depend on how fast your computer is and what other programs are running on it.)
You can look inside computation time to see how it works: Right-click (or control-click on a mac) the block and select "edit..." from the menu that appears.
computation time expression you just used to answer the previous question three more times and note the range of answers. They're not exactly the same because of other things that your computer is doing at the same time, so you should always take whatever result it gives you as approximate.
How long do you think it would take to count five-letter words if the list had 100,000 words?computation time to check using the 100,000 words list. The only way to answer a "How many words..." problem is to check every single word in the dictionary. So if you have ten times as many words in the dictionary, it takes ten times as long to check them all.
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.
Linear search does a complete traversal of the list. Binary search saves time by doing a partial traversal of the list.
Checking spelling 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 five-letter words), the best strategy 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.
to look for the word in the sorted list .png "100,000 words (sorted)")
.binary search block to see how it works.binary search with some words that you know are spelled correctly and some that you know are incorrect. binary search to search for the same words in the unsorted list 
. 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.
Two things affect whether you can use a binary search algorithm to make your program more efficient:
| 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 |
block included in your project, and look inside it. Compare it to the binary search algorithm you used to count the number of five- or seven-letter words (starting in the middle of a sorted list and repeatedly eliminating half the list). The linear search block does the same computation as the binary search block, but it uses the linear search algorithm.
to test how much time linear search takes to find the word "zebra" in each length list.
| Length of List | Linear Search Time |
|---|---|
| 1000 | |
| 10,000 | |
| 100,000 |
Look at the table. How would you describe what happens to the time as the input gets bigger?
The actual amount of physical time that it takes to solve a problem depends not only on your algorithm but also on how fast your computer is and what other programs you have running, etc. Therefore, computer scientists who want to measure the speed of an algorithm do it in terms of the number of steps. For example, what we really want to know about the efficiency of the linear search algorithm is how many times current item is compared to value (that is, how many times 
is called).
linear search algorithm for each length list?
| Length of List | Linear Search Time |
Linear Search Steps |
|---|---|---|
| 1000 | ||
| 10,000 | ||
| 100,000 |
How would you describe what happens to the number of steps as the input list gets bigger? Write your hypothesis about the pattern.The relationship between the input size and the number of steps required to solve a problem is the efficiency of the algorithm used to solve the problem.
Counting the number of steps, as you just did, is an informal, but perfectly good way to determine the efficiency of an algorithm. The formal measurement of an algorithm requires a mathematical proof.
binary search takes to find the word "zebra" in the sorted lists, and determine how many comparisons are made by the algorithm if "zebra" is the last word in each length list.
| Length of List | Binary Search Time |
Binary Search Steps |
|---|---|---|
| 1000 | ||
| 10,000 | ||
| 100,000 |
Describe what happens to the time and the number of steps as the input list gets bigger. Write down your hypothesis.linear search and the binary search algorithm, and compare the two search algorithms:
