Binary Search Topic 4.3.17 / Core / 2 lessons
Key points
  • making searches more efficient;
  • binary search
Vocabulary
  • binary search; <
  • <
  • <
Resources
  • Eck 7.4 Searching and Sorting.
Related topics

Starter

Given 100 numbers to look through, what is the worst case scenario number you will have to look at to find the one you want (or know it is not there)?

Tasks
  1. Follow through this presentation on Binary search.
  2. There is an online demonstration of a binary search here.
  3. ArrayBinarySearch is an example of a project involving a binary search. There is no fillArray() method - the values are entered manually since they need to be in order. Why would a findMax() method be redundant here?
  4. How do these two search methods compare for
    a. speed and
    b. complexity?
  5. Here is a Word document summarizing how to write a binary search in Java.
  6. Explain why data must be ordered if a binary search is used. [2 marks] (May 2006 SL P1 q6)