Analyzing and Improving Searches

Searching for an item in unsorted data is less efficient because you have to check every item, but it is easier to code.

unsorted list {1:20, 2:12, 3:3, 4:100, 5:50, 6: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.
    Find Number In Unsorted List
Searching unsorted data can become incredibly slow if we're dealing with an awful lot of data, but it is fairly 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 7.
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.
awful-list {1:1, 1:7, 3:8, 4:9, 5:11, 6:11, 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)
Al's note: this should look more like a "kid sketch" and not usable code. BK to MF or anyone else: How do I center an image?? BK to AC: these two images should use the same list; use 9 and not 9.3. BK tech glitch: in building this, when I try to place the sidenote inside the dialog, it cuts out the remaining "span" name callouts. For now the sidenote is outside the dialog box.
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.
Both position in sorted list and the number guesser algorithm can be built with the same binary search algorithm. How does this connect to the use of the word binary in Unit 4?
  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
    • the number of guesses it takes to find the number
  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.
    position of number (11) in sorted list (awful list)
    position of number (2) in sorted list (awful list)
  1. Make a table that tracks the number of guesses it takes to find the last number in a sorted list depending on the length of the list:
    Length of List Number of Guesses
    3
    7 3
    15
    63
    127