L2 Slides – Algorithms.pdf

Lesson 5: Binary search Algorithms  Starter activity Guess the number You are guessing the number that someone is thinking of between 1-15. The only feedback you get from the person is “correct”, “higher” or “lower”. For the...

Lesson 5: Binary search Algorithms  Starter activity Guess the number You are guessing the number that someone is thinking of between 1-15. The only feedback you get from the person is “correct”, “higher” or “lower”. For the first attempt you guess 8 and the person replies “lower”. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Questions: What number will you guess next? What would be the maximum number of guesses needed for 15 numbers? Think, write, pair, share.  Objectives Lesson 5: Binary search In this lesson, you will: Describe how binary search is used for finding the position of an item in a list of items Perform a binary search to find the position of an item in a list Identify when a binary search can and cannot be carried out  Activity 1 Using feedback to find a number The most efficient way to find a number based on the feedback “correct”, “higher” or “lower” is to check the middle number each time. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 If the middle number is correct then you are done. If the middle number is lower, you can ignore all the numbers after it. If the middle number is higher, you can ignore all the numbers before it. You can repeat this process with the remaining numbers until you find the correct number. This is how a binary search works!  Activity 2 Binary search Binary search is a much more efficient way of searching through a list of items compared to a linear search. However, you can only use a binary search algorithm if the data is ordered i.e. smallest to largest. If the data that you have is unordered, you must either use a linear search algorithm or sort the data first.  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 5 23 28 47 52 68 73 77 90 Take an ordered list of data and an item that is being searched for (the search item)  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 5 23 28 47 52 68 73 77 90 Maintain a range of items where the search item might be found. Initially, set the range to be the entire list. The range is specified through the indices of the first and the last items in the range.  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 5 23 28 47 52 68 73 77 90 midpoint Find the item in the middle of the range (the midpoint item).  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 5 23 28 47 52 68 73 77 90 midpoint Compare the midpoint item to the item you are searching for.  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. Cup 6 Cup 7 Cup 8 Cup 9 52 68 73 77 90 midpoint If the midpoint item is less than than the search item, change the range to focus on the items after the midpoint. The items are arranged in order, so the search item cannot be found before the midpoint.  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. Cup 6 Cup 7 Cup 8 Cup 9 68 73 77 90 midpoint Find the item in the middle of the range (the midpoint item). If there is an even number of items, select the middle-left item.  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. Cup 6 Cup 7 Cup 8 Cup 9 68 73 77 90 midpoint Compare the midpoint item to the item you are searching for.  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. 73 midpoint If the midpoint item is greater than than the search item, change the range to focus on the items before the midpoint. The items are arranged in order, so the search item cannot be found after the midpoint.  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. 68 midpoint Find the item in the middle of the range (the midpoint item). If there is only one item left, select this item.  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. 68 midpoint Compare the midpoint item to the item you are searching for.  Activity 2 Binary search Each number is hidden under a cup. The cups are arranged in order with the lowest value on the left. The number to find is 68. 68 midpoint If the item at the midpoint is equal to the search item, then stop searching.  Activity 2 Algorithm for binary search 1. Take an ordered list of data and an item that is being searched for 2. Maintain a range of items where the search item might be found. Initially, set the range to be the entire list. 1. Repeat steps a-e until you find the item you are searching for or there are no more items to check (the range is empty): a. Find the item in the middle of the range (the midpoint item). b. Compare the midpoint item to the item you are searching for. c. If the midpoint item is equal to the search item, then stop searching. d. Otherwise, if the midpoint item is less than than the search item, change the range to focus on the items after the midpoint. e. Otherwise, if the midpoint item is greater than than the search item, change the range to focus on the items before the midpoint.  Activity 3 Searching ordered cards You are now going to perform a binary search on a set of cards: 1. Take 10 cards and choose a card to search for 2. Put the cards in order from lowest to highest 3. Place 8 of the 10 cards face down in a single row without looking at them 4. Perform a binary search for your chosen card and fill in the table Rules: you can only turn over one card at a time. You must turn it back over after each comparison. Follow the instructions in groups of 2 or 3 and answer the questions on the Activity 3 worksheet.  Activity 4 Performance of binary search Binary search is a very powerful algorithm because of how fast it is. In the previous examples, you saw that with each comparison, the algorithm eliminates half of the data. That means if you had 1000 items to search through, it would take at most 10 comparisons for a binary search to find an item. If you doubled that number to 2000 items, it would only increase the most number of comparisons by one!  Activity 4 Performing a binary search Complete the tasks on the Activity 4 worksheet for performing a binary search.  Plenary Ordered and unordered data When faced with a data searching problem, you will either have to deal with ordered or unordered sequences of items. Questions: 1. Does data need to be in sequence for you to perform a linear search on it? 2. Can you perform a binary search on a list of unsorted items? 3. Why are phone books and dictionaries sorted?  Summary Next lesson In this lesson, you… Next lesson, you will… Described how binary search is used Investigate a sorting algorithm for finding the position of an item in called bubble sort. a list of items. Performed a binary search to find the position of an item in a list. Identified scenarios when a binary search can and cannot be carried out.