Binary Search Trace

Binary Search Trace

Binary search is a method for finding a target in a sorted list by repeatedly narrowing the search interval. A trace asks you to show how the interval changes at each step and what happens to the middle element.

How to work through a trace

1. Check that the list is sorted. Binary search only works correctly on ordered data.
2. Set the initial bounds. Start with the first and last positions of the searchable part of the list.
3. Find the middle position. Compare the target with the middle value.
4. Decide the next interval.
   • If the target is smaller, keep the left half.
   • If the target is larger, keep the right half.
   • If it matches, stop.
5. Repeat until the target is found or the interval becomes empty.

How to simplify the final answer

Your final response should usually be the result of the search trace written clearly: the found position, the number of steps, or the final interval/state after the last comparison. If there are repeated values or edge cases, keep the exact outcome shown by the search process.

Quick check

Make sure each step follows the previous one logically, and that the interval always gets smaller. If the target is found, the final middle value must equal it; if not, the search should end with no valid interval left.