Example 1 — Trace a binary search
Show the steps and the answer
Start with the whole range, indexes 0 to 7. The middle is (0 + 7) ÷ 2 = 3.5, rounded down to 3, which holds 19.
Checking the middle splits the remaining items into two halves of nearly equal size.
31 > 19, so the range becomes indexes 4 to 7.
The list is sorted, so every item at index 3 or below is 19 or less and cannot be 31.
New middle: (4 + 7) ÷ 2 = 5.5, rounded down to 5, which holds 31. Found at index 5.
One comparison removed half the list, and the second landed on the target.
Linear search checks 3, 8, 12, 19, 24, 31: 6 checks.
It cannot skip anything, so it reaches index 5 only after looking at every item before it.
Answer: Binary search finds 31 at index 5 after 2 checks; linear search needs 6.
Takeaway: Each binary-search check halves the range, and sorted order is what makes discarding a half safe.