Why binary search needs order

How can one comparison rule out half the possibilities?

Adapt this plan

Keep only the interval that can contain the target.

Find Indices start at 0

The outlined cell is the current comparison. Faded cells have been ruled out.

Check the explanation

A sorted list of distinct integers. Each step displays one comparison. Array indices start at zero.

Teaching notes · 25 minutes

Students should be able to…

Explain which half can be discarded after a comparison, and why the input must be sorted.

Before this lesson

Reading an array, comparing integers, and identifying an index.

Ask first

You need to find 42 in a sorted list. Which value would you inspect first, and why?

A misconception to listen for

Halving the list is valid only when its order lets you rule out every value on one side. Choosing the middle of an unsorted list gives no such guarantee.

Student task

Draw the remaining interval after every comparison for targets 7 and 75. Then rearrange the list and explain which justification fails.

Exit question & expected reasoning

The middle value is 31 and the target is 42. Why can the left half be discarded?

Every value to the left is at most 31 because the list is sorted. None can equal 42, so search continues strictly to the right of the middle.

Continue in Research Labs