Study guide: Prepare and Compare Searches
Sort data, count search inspections and trace a first-match binary-search variant.
Ideas to explain in your own words
- Count comparisons and handle an absent target in an unsorted list.
- Build a sorted prefix and preserve all supplied items.
- Explain how sorted order allows part of a search range to be discarded.
- Trace a lower-bound search with explicit half-open ranges.
Watch your reasoning
- The target is at zero-based position 2, after inspecting positions 0, 1 and 2: three inspections.
- Only key 4 has been inserted into the initial prefix [7]. The last item 6 is not processed until the next pass.
- The first middle is 18. Since 9 is smaller, the remaining range is [4, 9, 13], whose middle is 9. The reasoning relies on the supplied sorted order.
- All earlier values are less than 7, and position 4 holds 7. The lower-bound result is position 4 and equality confirms a match.
A worked review example
Trace a Linear Search: Target 5: inspected values 8 → 3 → 11 → 5; return position 3 after 4 inspections. Target 7: inspect all 5 items, return not found. A position and a count differ by one in this first-match case. Trace Insertion Sort: Arrays after passes: [2, 6, 5, 3] → [2, 5, 6, 3] → [2, 3, 5, 6]. The final array is sorted and its items match the original multiset. There are 1 + 1 + 2 = 4 right-shifts of larger items. Trace binary search in a sorted list: Target 31 is larger than 18, so the left side and 18 are discarded. The remaining middle is 31, which matches. Two item inspections found the target. Find the First Matching Sorted Position: Target 4: (lo,hi)=(0,6), mid 3 value 4 → hi 3; mid 1 value 4 → hi 1; mid 0 value 2 → lo 1. Stop at position 1, first 4. Target 5 inspects 4,9,7 and stops at insertion position 4; value 7 is not equal, so report not found.
Make a practice plan
- Try the supplied lesson problems without looking at the answers.
- Compare your method with the worked examples and explain any correction.
- Use the new review cases, then complete the transfer task on paper or in your own document.