Searching Algorithms

Why halving works

• Order-based elimination: If the target is less than the pivot in ascending order, every item after the pivot is impossible and can be rejected. If the target is greater, every item before the pivot is impossible, so one comparison removes many candidates.
• Invariant idea: After each step, the target can only be inside the updated bounds if it exists at all. Maintaining this invariant is why binary search remains both correct and efficient.

Complexity logic

• Logarithmic reduction: After $k$ comparisons, the candidate size is roughly $\frac{n}{2^k}$, so the number of steps grows slowly as data grows. This gives the familiar complexity $O(\log_2 n)$ for successful and unsuccessful searches in sorted arrays.

Key relation: $k \approx \lceil \log_2 n \rceil$ comparisons in the worst case, where $n$ is list length and $k$ is comparison count.

Binary search procedure

• Initialize bounds: Start with left bound $L$ at the first position and right bound $R$ at the last position of the ordered list. Then compute a middle position, commonly $m = \left\lceil \frac{L+R}{2} \right\rceil$ in one-based exam methods.
• Compare and shrink: If target equals pivot, stop with success; if target is smaller, set $R = m-1$; if larger, set $L = m+1$. Repeat until found or until bounds cross, which proves absence.

Completion and correctness checks

• Stopping conditions: The algorithm ends when either a match is identified or the candidate interval becomes empty. An empty interval means no position can still contain the target, so a "not in list" conclusion is logically valid.
• State tracking: Writing each reduced sub-list or updated bounds prevents hidden mistakes in manual work. This also makes it easy to justify the final statement that the search is complete.

Binary search vs linear search

• Core trade-off: Linear search works on unsorted data but may inspect many items, while binary search needs sorted data but is much faster on large lists. Method choice therefore depends on whether sorting is already available or justified by repeated queries. | Feature | Linear Search | Binary Search | | --- | --- | --- | | Data requirement | Any order | Must be ordered | | Worst-case checks | $n$ | about $\lceil \log_2 n \rceil$ | | Typical use | One-off scan | Repeated lookups on sorted data |

Comparison-rule distinctions

• Ascending vs descending order: The branch direction reverses when list order reverses, so "smaller goes left" is not universal. Always anchor decisions to the stated order rule before eliminating a half.
• Found vs not found outcomes: A successful search ends at equality with pivot, while an unsuccessful one ends when no valid interval remains. These are different completion states and should be reported explicitly.

Frequent logical errors

• Using binary search on unsorted data: This breaks the elimination logic because comparisons no longer imply anything about unseen positions. The algorithm may terminate, but the conclusion is not reliable.
• Incorrect bound updates: Keeping the pivot in the next interval after a strict less-than or greater-than comparison can cause loops or repeated checks. Correct updates use $m-1$ or $m+1$ so the interval strictly shrinks.

Notation and interpretation mistakes

• Confusing value with position: Students often mix pivot value and pivot index, then reject the wrong side. Keep "where" (index) and "what" (value) separate throughout the working.
• Missing the unsuccessful end state: Some solutions stop when one item remains without proving absence. You must explicitly reject the final interval or show crossed bounds to justify "not found."