Analyzing and Improving Searches

Brian wants to rename this page "Searching a List." --MF, 2/19/18

On this page, you will see how the characteristics of a list can affect the algorithm for searching in it.

Searching in Unsorted Data

When searching for an item in unsorted data, you have to check every item until you find the value you are looking for.

unsorted list {20, 12, 3, 100, 50, 12}
  1. Build a position of number in unsorted list block that reports the earliest location of a number in an unsorted list or reports "Not In List" (or NIL, if you like) if the number is not in the list.
    position of number (12) in unsorted list(list{20,12,3,100,50,12}) reporting 2
Searching unsorted data can become slow if we're dealing with a lot of data, but it is quick when working with short lists.

Searching in Sorted Data

If you are searching for a number in a sorted list, you have more information. Suppose you have a sorted list and you want to locate the position of a number.

Typically, sorted lists are from lowest to highest. You'll create a block that sorts a list of numbers in Unit 8, Sorting a List.
Alphie: If the list is sorted, we could look at the middle element of the list and see if our number is in the first or last half of the list. That would save time.
Betsy: This feels a lot like the guessing game we built—I pick a number and the computer tries to guess it by splitting the list in half with each guess.
Brian wants us to scrub the list name "awful list" from the curriculum, and Mary agrees. --MF, 2/22/18
awful-list {1:1, 1:7, 3:8, 4:9, 5:11, 6:12, 7:21, 8:22, 9:23, 10:24, 11:73, 12:73, 13:96, 14:99}
Alphie: But in that one, the computer guessed a number that we picked. Now we want it to find a number in a list and report its position. It should work like this:
position of number (11) in sorted list (awful list) reporting 5
Betsy: Yes, but it still feels the same. It should have the same guts as the guessing game.
Betsy's last remark is a version of abstraction. Betsy noticed that position in sorted list and the number guesser algorithm should have the same overall structure.
  1. Using the strategy of your guessing game project from the previous page, write a block that says:
    • the position of an item in an ordered list, and,
    • the number of guesses it takes to find the number
      • say position of number (11) in sorted list (awful list) sprite saying 'Position is 5, found in 4 guesses'
    If the number is in the list more than once, any one that you find is ok.
  2. Then, build a position of number in sorted list block that returns the position of a number in a list sorted from lowest to highest or zero if the number is not in the list. (Note: This task is identical to the previous one except that instead of the block "saying" the position it will need to "report" the position.)
    position of number (11) in sorted list (awful list) reporting 5
    position of number (2) in sorted list (awful list) reporting 0
  3. Compare position in sorted list with position in unsorted list:
    1. Which runs faster for large inputs?
    2. Which has more blocks in its code?
  1. Make a table that tracks the number of guesses it takes to find a number in a sorted list depending on the length of the list if that number turns out to be the last item.
    Length of List Number of Guesses
    3
    7 3
    15
    63
    127