Binary Search on Sorted Data · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Half the suspects each round

Computing · Programming · ages 15-16
Name ______________________   Date ____________

  1. What happens in one round of binary search?

    • Check every item in turn
    • Compare the middle, then drop the dead half
    • Shuffle the list and retry

  2. Binary search needs its data sorted.

    Circle one:   True   False

  3. Each comparison wipes out about half of the suspects left.

    Circle one:   True   False

  4. Why does halving fail on jumbled data?

    • Jumbled lists cannot be read
    • Comparisons stop working
    • The dropped half might hide the target

  5. Hunting 57 in sorted 3, 37, 45, 57, 93 and 120, the middle reads 45. Which half survives?

    • The upper half holding 57, 93 and 120
    • The lower half holding 3, 37 and 45
    • Both halves stay in play

  6. When is the sorting cost worth paying?

    • When only one hunt is planned
    • When many hunts will follow
    • When the list keeps shrinking

  7. A thousand sorted items face one hunt by each method. What best compares them?

    • About ten halvings against up to a thousand checks
    • Ten checks each either way
    • A thousand checks each either way

  8. A friend runs binary search on unsorted scores and trusts the miss. What do you say?

    • Trust it, since halving never fails
    • Add more items and retry
    • Sort first, since a miss on jumbled data proves nothing
LightMySky · lightmysky.comW1-mt_3avV-VasFZ-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Half the suspects each round W1-mt_3avV-VasFZ-s1

  1. Compare the middle, then drop the dead half · One middle comparison kills about half the suspects.
  2. True · Halving only trusts ordered data.
  3. True · Only the half that can still hold the target survives.
  4. The dropped half might hide the target · Without order, the thrown half may hold exactly what you hunt.
  5. The upper half holding 57, 93 and 120 · 57 tops the middle 45, so only the upper half can hold it.
  6. When many hunts will follow · Upfront sorting pays off across many later hunts.
  7. About ten halvings against up to a thousand checks · Halving melts a thousand suspects in about ten rounds.
  8. Sort first, since a miss on jumbled data proves nothing · On jumbled data the method is broken, so its misses mean nothing.
Worksheet · LightMySky