Unit 5: Day 7
START DATE:DUE DATE:STATUS:Open
Tasks
58.1 Introduction to Binary Search
- Review the search algorithm/function we created with the weather example. This function used what is called a linear or a sequential search algorithm. But there are alternative search algorithms.
- Use the video about search algorithms on this website and then use its corresponding searching page to talk about the difference between linear and binary search algorithms.
- Be sure to stress that data must be SORTED for binary search to work. Note that sorting algorithms are not part of this course but there is a built in arrays sort algorithm available.
- Have students play the “higher/lower guessing game” in pairs with numbers between 1 and 100.
- After a few rounds have students explain their approaches.
- One approach will be dividing the numbers in half with each guess (Start at 50, if higher guess 75, if lower guess 25, etc.)
- If no students guess its, present an approach that starts at 1 and increments with each guess
- Do all approaches work?
- What’s the maximum number of guesses for each approach?
- Approach #1 - log (base 2) of 100 (dividing in half each time)
- Approach #2 - 99 guesses
- After a few rounds have students explain their approaches.
58.2 Translator Assignment
- Instructions for this assignment can be found in the folder: 1.6 Year 1 - AP Extensions
- This assumes the use of linear search but could be adapted now that you have also introduced binary search.
- Review AP Concepts:
- AAP-2.O.1: Traversing a list can be a complete traversal, where all elements in the list are accessed, or a partial traversal, where only a portion of elements are accessed. EXCLUSION STATEMENT (EK AAP-2.O.1): Traversing multiple lists at the same time using the same index for both (parallel traversals) is outside the scope of this course and the AP Exam.
- AAP-2.O.2: Iteration statements can be used to traverse a list.
- AAP-2.O.5: Linear search or sequential search algorithms check each element of a list, in order, until the desired value is found or all elements in the list have been checked.
Continue to Unit 5: Day 8 »
