Intermediate · Module 9 · Lesson 1
Exact target search
Discard half after comparing with the middle.
Lesson 47 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Binary Search laboratory
Compare exact, boundary, and answer-space search
Range
10
Comparisons
1
Upper bound
4
Result
4
12 equals 12. Index 4 is the answer.
If 12 exists, it is inside indexes 0…9.
Binary search needs a monotonic decision
Binary search is possible when one comparison divides the remaining candidates into an impossible side and a possible side. A sorted array provides that monotonic order: if values[mid] < target, every index at or left of mid is too small.
Sorted input is a correctness condition
Trace one complete search
Search for 23 in [3, 7, 11, 18, 23, 31, 42] using a closed interval [low, high]. Every update must remove mid, because that value has already been compared.
| low | high | mid | values[mid] | Decision |
|---|---|---|---|---|
| 0 | 6 | 3 | 18 | 18 < 23, so low = 4 |
| 4 | 6 | 5 | 31 | 31 > 23, so high = 4 |
| 4 | 4 | 4 | 23 | Target found at index 4 |
Active Recall Checkpoint
Why must the loop use low <= high for a closed interval?
Hint: Consider the state where one candidate remains.
Show answer & explanation
When low == high, one valid candidate is still inside the search range and must be inspected.
Keep one interval convention from start to finish
int binarySearch(int[] values, int target) {
int low = 0;
int high = values.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (values[mid] == target) return mid;
if (values[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}- 01Empty input exits immediately because
highbegins at -1. - 02Compute the midpoint as
low + (high - low) / 2to avoid adding two large indexes. - 03Move past
midafter a mismatch so the interval strictly shrinks. - 04Use a different return contract when duplicate values require the first or last occurrence.
Derive logarithmic time instead of memorizing it
After k comparisons, at most n / 2^k candidates remain. The search ends when that quantity reaches one, so 2^k ≥ n and k ≥ log₂ n. Iterative binary search therefore uses O(log n) time and O(1) auxiliary space.
Use it when
Use binary search when candidates are ordered or a feasibility predicate changes only once across an answer range.
Reconsider when
Use a linear scan for tiny or unsorted inputs unless sorting is independently useful; sorting solely for one search costs O(n log n).
Cost Model
Complexity & Trade-offs
When to use it
- Exact lookup, first/last occurrence, rotated order, and answer-space optimization.
- Any monotonic yes/no feasibility boundary.
- Implicit ordered spaces where values need not be materialized.
Common mistakes
- Mixing inclusive and half-open interval updates.
- Using binary search without proving monotonicity.
- Returning the last middle value instead of the stored boundary.
Practice prompts
- Reproduce the worked Exact target search example without looking at the trace.
- Change one input condition and explain whether the Exact target search invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check