Lessons‎ > ‎

LP-Search Algorithms

Topic: Searching 

Objectives:  Students will be able to:
  • understand simple examples of searching algorithms and when they may be applied.
  • understand the details of binary and linear searches.
  • analyze the differences in efficiency of the different algorithms.
CS Principles Learning Objectives: Students will be able to:
  • 4.3.1 Appropriately connect problems and potential algorithmic solutions. [P1]
  • 4.4.1 Evaluate algorithms analytically and empirically. [P4]
Essential Knowledge: Students need to know:
  • 4.3.1.a Searching for an item in a list can be solved in a reasonable time by using a binary search when the list is sorted; otherwise, it can be done with linear search.
  • 4.4.1.b Different correct algorithms for the same problem can have different efficiencies.
Outline:
  • Lesson Starter (5 minutes):  Can you guess a number between 1 and 1000, within 10 guesses, if you know whether each guess is too high or too low? (Binary search)
  • Activity (10 minutes): Search activity.
  • Explanation (20 minutes):  Express in pseudocode the binary search  and linear search algorithms used in the activity. Chart and graph the efficiency of each algorithm.
  • Videos (If time permits): Watch and discuss videos on searching algorithms.
  • Wrap up (5 minutes):  Review, reflection, and assessment.
Details:
  • Lesson Starter: Can you guess a number between 1 and 1000, within 10 guesses, if you know whether each guess is too high or too low?
    • Try this with the students. Tell them you are thinking of a number between 1 and 1000 and have them guess your number within 10 guesses.
    • How did we know that 10 guesses is enough?  
      • Answer: 1000 < 210.  We arrive at a single number if we divide the range in half 10 times. That is, 210 = 1024, which is greater than 1000.  Each guess will divide the range in half, from 1000 numbers to 500 to 250 to 125 to 63 to 32 to 16 to 8 to 4 to 2 to 1.  That's 10 divisions. This method is known as binary search.
    • How many guesses do we need to guess a number between 1 and 100?  Between 1 and 1,000,000?   
      • Answer: Start by filling in the first few columns of this powers-of-2 table. Then have the students complete the table. As x increases by 1, then 2x doubles in size. You can see that it would take at most 7 guesses to guess a number between 1 and 100 and 20 guesses to guess a number between 1 and 1,000,000.
 x  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  
 2x  1  2  4  8  16  32  64  128  256  512  1024  2048  4096  8192  16,384  32,768  65,536  131,072  262,144  524,288  1,048,576  

  • Activity: Give the students two sets of data, one sorted and the other random. Ask them to describe algorithms they would use to look up a value in each set. 
    • Data set #1:  If you had a list of 1 million phone numbers in no particular order, how would you determine whether your phone number is on the list? You're not allowed to rearrange the list. What's the algorithm? Describe your algorithm in pseudocode.
      • Answer: This would require a linear search. Since the list is unsorted, you would need to start either at the top or the bottom and search one by one until you find your number.
    • Data set #2:  If you had a list of 1 million names arranged in alphabetical order, how would you determine whether your name is on the list?  What's the algorithm? Describe your algorithm in pseudocode.
      • Answer: This would require a binary search. Since the list is sorted (i.e. in alphabetical order), you can skip to the middle of the list and determine whether the name in the middle is before or after yours. Repeat until you find your name. Similar to the guessing game.
  • Explanation:  Express in pseudocode the binary search  and linear search algorithms. Show the students the pseudocode (in order) and use the provided explanations to walkthrough and explain the pseudocode. It may be helpful to explain the pseudocode using the two data sets in the previous activity.
  • Binary Search Algorithm in Pseudocode:  Find where some X occurs in the list L. We assume the list L is sorted in ascending order.  The value can be anything -- i.e., a number, a letter of the alphabet, a word, etc.   'Where in the list' means 'at what index' and we assume the list L is indexed starting at 1. For binary search, we check the middle value in the list.  If it is X then we return its index.  If it is greater than X, then X can't be in the top half of the list, so we cut off the top half and do binary search on the bottom half of the list.  If it is less than X, then X can't be in bottom half of the list, so we cut of the bottom half and do binary search on the top half of the list. Here's how this would be written in pseudocode:
# Search for X in a sorted list L and return its index in L
# Or return -1 if X is not in the List
To Search for X in a sorted List, L, with indexes ranging from 1 to N.
   Set  low to 1
   Set high to N                        # Low and high refer to the lowest and highest indexes in the list or sublist
   Set middle to (low + high) / 2       # Find the integer average of low plus high. That's the index of the middle element
   Repeat until you find X or until you can no longer divide the list in half
     If the item at middle = X:
       Return middle and stop           # Found X, so its index is middle
     Else if item at middle < X:        # X can't be in the bottom half of the list, so cut off the bottom half
       Set low to middle + 1            # Cutting of bottom half, so set low to the first index in the top half of the list
     Else: 
   Return -1                            # We can no longer divide the list in half and haven't found X so return -1   
    • Linear Search Algorithm in Pseudocode:  Find where some X occurs in the list L. We assume the list L is not sorted, meaning the contents of the list can be in any order whatsoever.  The value X can be anything -- i.e., a number, a letter of the alphabet, a word, etc.   'Where in the list' means 'at what index' and we assume the list L is indexed starting at 1. For linear search, we check whether the first number (index = 1) is the X we are searching for.  If so, we return 1 (its index). If not, we look at the next number, continuing in this way until we find X or reach the end of the list. Here's how this would be written in pseudcode:
# Search for X in List L and return its Index, index,  in  L
# Or return -1 if X is not in the List
To Search for X in an unsorted List L, DO:
        Set indx to 1
        For the item at indx in the list, L:  # Check the item at indx
          If item = X:
            Return indx and stop     # Found X, so return its index
          Set indx to indx + 1       # Keep searching
        Return -1                    # We've searched all N items. Returning -1 means that X wasn't in the list L  
    • Draw a table to show the efficiency of these two algorithms.  
      • Complete the following table and graph the results on the board, showing the difference in growth rates between linear and logarithmic rates. Ask the students to identify which search algorithm is more efficient.
 Number of elements N
Maximum number of lookups 
Linear Search
             (Linear Rate)
Maximum number of lookups 
Binary Search
            (Logarithmic Rate)
 10 10 4
 100 100 7
 1000 1000 10
 10000 10000 14
 100000  100000 17
 1000000 1000000 20

    n = linear rate            log(n) = logarithmic rate
  • Videos: If time permits, the Related Resources and Activities section below contains some videos that would be useful to view and discuss.
  • Wrap Up: Review the two types of searching algorithms: Searching for an item in a list can be done with binary search when the list is sorted; otherwise it can be done with linear search. Have the students write a reflection in their portfolio and complete the interactive exercises.
Assessment
Notes for Teacher:
Logarithms:  To understand how efficient binary search is, it is useful to understand base 2 logarithms.  The log base 2 of some number X is the power you have to raise 2 to in order to get X.  For example, 23 = 8, so the log2(8) = 3.  And 210 = 1024, so the log2(1024) = 10.  Here's a nice resource for this concept.  And here is a graph from that page, which shows that log(x) is a function that grows very slowly as x gets larger and larger.  That is why the binary search algorithm is so efficient.


Reflection for the Teacher (Learn Adapt Teach Reflect):

  1. Is there anything else you would need to have or know to teach this lesson effectively?
  2. What specific elements of this lesson (examples, activities, etc.) would you change?

  3. How would you modify or add to the interactive exercises (formative assessments)?

Related Resources and Activities:

  • Searching and Sorting lecture notes from Trinity's Mobile CSP course. 
  • Binary Search Algorithm on Wikipedia
  • Linear Search on Wikipedia
  • Interactive binary search demo -- Give a list of state abbreviations arranged in alphabetical order (e.g., CT, NY), this demo traces the binary search algorithm as you search for different abbreviations in the list.
  • Interactive binary search demo with Pascal code -- This demo includes displays the binary search algorithm in Pascal, which isn't all that different from the pseudocode we've used in other algorithm examples.
  • Binary and Linear Search Algorithms (6:24 video)
    This videos visually shows how the binary and linear search
     algorithms are executed. It shows how to search for a particular integer in an array of integers, shows some pseudocode, and talks about the speed and efficiency of each algorithm with comparisons.
  • Linear Search (3:32 video) This video provides some real life examples of linear searching along with searching for a number in an array. The video also discusses the pseudocode and how a linear search is performed.