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 the first item, then drop it and move on
    • 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
    • The middle item cannot be found without order
    • The dropped half might hide the target

  5. Hunting 12 in sorted 2, 5, 12, 18, 25, 31 and 40, the middle reads 18. Which part stays in play?

    • The lower part: 2, 5 and 12
    • The upper part: 25, 31 and 40
    • Both parts 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. Four thousand sorted items face one hunt by each method. What best compares them?

    • About 12 halvings against up to 4,000 checks
    • About 2,000 halvings against up to 4,000 checks
    • 4,000 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 lower part: 2, 5 and 12 · 12 is below the middle 18, so only the lower part can hold it. 18 and everything above it drop away.
  6. When many hunts will follow · Upfront sorting pays off across many later hunts.
  7. About 12 halvings against up to 4,000 checks · Each halving cuts the range in two, and 2 to the 12th is 4,096, so about 12 rounds cover 4,000 items. One-by-one may need all 4,000.
  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