Searching Algorithms: Linear and Binary Search For students.

Searching means finding whether an item is in a collection and where. Linear search checks items one by one from the start — simple, works on any list. Binary search is cleverer: on a sorted list it checks the middle, discards the half that cannot hold the target, and repeats, halving the space each step.

Searching is the most common operation in computing. Every dictionary lookup, "find in page", and database query is a search. The jump from linear to binary search shows how a smarter algorithm — not a faster computer — makes an impossible task instant.

Key Concepts

• Linear search: scan from index 0, comparing each element; stops at the first match. Works on unsorted data.
• Binary search: needs sorted data; repeatedly checks the middle and discards half.
• low, mid, high: the three pointers; mid = low + (high − low) / 2 — the subtraction form avoids overflow that low + high can cause.
• Complexities: linear is O(1) best, O(n) average/worst; binary is O(1) best, O(log n) average/worst.
• Sorted precondition: binary search on unsorted data gives wrong answers; sorting first costs O(n log n), paying off only with many searches.
• Halving: after k binary-search steps at most n / 2^k elements remain.

Formulas

• Midpoint: mid = low + (high − low) // 2. For low = 0, high = 14: mid = 7.
• Max comparisons: floor(log2 n) + 1. For n = 1,000,000 that is 20 comparisons worst case.
• Linear search: worst case n comparisons, average (n + 1) / 2 when the target is present.
• Speedup: for n = 1,000,000, ~20 binary steps versus ~500,000 linear steps on average — about 25,000× fewer comparisons.
• Decision rule: unsorted data searched once → linear O(n) beats sort-then-search O(n log n); searched many times → sort once, binary-search forever.

Worked Example

Find 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0–9). Step 1: low = 0, high = 9, mid = 4; A[4] = 16 < 23 → low = 5. Step 2: mid = 5 + (9−5)//2 = 7; A[7] = 56 > 23 → high = 6. Step 3: mid = 5; A[5] = 23 — found at index 5 in 3 comparisons (linear search needed 6). Search for 40 (absent): mid = 4 → 16 < 40, low = 5; mid = 7 → 56 > 40, high = 6; mid = 5 → 23 < 40, low = 6; mid = 6 → 38 < 40, low = 7. Now low > high, so 40 is absent — decided in 4 comparisons.

Common Misconceptions

• "Binary search works on any array." Wrong — on unsorted data it can miss a present target. Sorted input is non-negotiable.
• "Binary search is always better." Wrong for one-off searches of unsorted data, where sorting first costs more than a linear scan.
• "mid = (low + high) / 2 is fine." In fixed-size integers, low + high can overflow on huge arrays; low + (high − low) / 2 is the safe form — a real historical bug.

Real-World Applications

• Linear search: small or unsorted lists, and scans inside other algorithms.
• Binary search: dictionary lookup, sorted database indexes, Python's bisect module.
• Variants: first/last occurrence of duplicates, rotated sorted arrays, guessing games.
• The halving idea: binary search trees and git bisect, which finds the bug-introducing commit.

Linear search is the honest plodder — always works, always O(n). Binary search is the clever halver — O(log n) on sorted, randomly-accessible data. Twenty smart steps can replace a million dumb ones: that is the deepest lesson in algorithms.