Binary search — iterative, recursive; O(log n); searching in sorted - rotated arrays

WHY binary search exists

Think of guessing a number between 1 and 1000. Guess 500: "higher/lower" reply kills 500 numbers. Ten guesses ($2^{10}=1024$) is enough. That's the whole trick.

WHAT it is

HOW — deriving the loop from first principles

We maintain a window [lo, hi] that is guaranteed to contain the target if it exists at all. This is the invariant — everything else follows from protecting it.

1. Start: lo = 0, hi = n-1 (whole array).
2. Pick mid between them. Why mid? It splits the window as evenly as possible, so the worse half is as small as possible → fewest steps in the worst case.
3. Compare arr[mid] to target:
   • equal → found, return mid.
   • arr[mid] < target → target (if present) is to the right, so lo = mid + 1. Why +1? mid itself was just ruled out; keeping it risks an infinite loop.
   • arr[mid] > target → hi = mid - 1 for the same reason.
4. Stop when lo > hi (empty window) → not found.

Iterative code

def bsearch(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:                 # window non-empty
        mid = lo + (hi - lo) // 2   # overflow-safe
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1            # discard left half incl. mid
        else:
            hi = mid - 1            # discard right half incl. mid
    return -1

Why lo <= hi not lo < hi? When lo == hi the window still has one element we haven't checked — dropping it would miss single-element matches.

Recursive code

def bsearch_rec(arr, target, lo, hi):
    if lo > hi:                     # base case: empty
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return bsearch_rec(arr, target, mid + 1, hi)   # right
    return bsearch_rec(arr, target, lo, mid - 1)       # left

Same logic; the call stack replaces the loop. Recursion depth is $O(\log n)$, so memory is $O(\log n)$ vs $O(1)$ for iterative.

WHY it is $O(\log n)$ — derived

Let $T(n)$ = comparisons in the worst case for $n$ elements. Each step does $O(1)$ work then recurses on half: $T(n) = T(n/2) + 1,\qquad T(1)=1$ Unrolling: $T(n) = 1 + 1 + \dots$ until $n$ shrinks to $1$. Number of halvings $k$ satisfies $n/2^k = 1 \Rightarrow 2^k = n \Rightarrow k = \log_2 n$. So $\boxed{T(n) = \log_2 n + 1 = O(\log n)}$ Space: iterative $O(1)$, recursive $O(\log n)$ (stack).

Searching in a ROTATED sorted array

A sorted array rotated at a pivot, e.g. [4,5,6,7,0,1,2]. It's no longer globally sorted, but at least one half around mid is always sorted. We exploit that.

def search_rotated(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[lo] <= arr[mid]:                 # left half sorted
            if arr[lo] <= target < arr[mid]:    # target in left
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                   # right half sorted
            if arr[mid] < target <= arr[hi]:    # target in right
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Why <= in arr[lo] <= arr[mid]? When lo == mid (window size 1–2) the "left half" is a single element, trivially sorted; <= keeps that case correct. Still $O(\log n)$ — each step discards a half.

Worked examples

Common mistakes (steel-manned)

Flashcards

Connections

• Linear Search — $O(n)$ baseline; binary search beats it only when data is sorted.
• Sorting Algorithms — must sort first ($O(n\log n)$) to enable binary search.
• Logarithms — the inverse-of-halving that gives the complexity.
• Recurrence Relations — $T(n)=T(n/2)+1$ analysis.
• Time Complexity & Big-O — places $O(\log n)$ between $O(1)$ and $O(n)$.
• Lower & Upper Bound (bisect) — variants finding first/last position.
• Binary Search Tree — same divide idea as a data structure.

Concept Map

Hinglish (regional understanding)