Introduction

Binary search is one of the clearest examples of divide-and-conquer in everyday programming. It repeatedly cuts the search space in half until the target is found or the range becomes empty. The reason it is classified this way is not just speed, but the exact structure of its decision process.

Divide, Conquer, and Binary Search

A divide-and-conquer algorithm usually has three steps:

• Divide the problem into smaller parts.
• Conquer one or more subproblems recursively or iteratively.
• Combine sub-results into the final answer.

Binary search follows this template with a small twist: after dividing into two halves, it only needs to recurse into one half, because sorting lets it discard the other half safely.

For a sorted array:

• Divide: choose mid and compare arr[mid] with target.
• Conquer: continue in left half or right half.
• Combine: no heavy merge step is needed; the recursive return already carries the final answer.

So yes, combine is minimal, but the algorithm still matches divide-and-conquer structurally.

Why Halving Works

The power comes from sorted order. After comparing with the middle element:

• If target is smaller, every index to the right of mid is impossible.
• If target is larger, every index to the left of mid is impossible.

That logical elimination shrinks the candidate set from size n to about n / 2 each step.

After k steps, the remaining space is about n / 2^k. The process stops when this reaches 1, so k is about log2(n). That is the source of O(log n) time.

Iterative Implementation

Binary search is often written iteratively for clarity and stack safety.

1def binary_search(arr, target):
2    low = 0
3    high = len(arr) - 1
4
5    while low <= high:
6        mid = low + (high - low) // 2
7        value = arr[mid]
8
9        if value == target:
10            return mid
11        if value < target:
12            low = mid + 1
13        else:
14            high = mid - 1
15
16    return -1
17
18
19data = [2, 4, 7, 9, 14, 18, 21, 30]
20print(binary_search(data, 14))  # 4
21print(binary_search(data, 5))   # -1

The midpoint expression avoids potential overflow in fixed-width integer languages.

Recursive Form and the Recurrence

The recursive shape makes the divide-and-conquer nature explicit.

1def binary_search_recursive(arr, target, low, high):
2    if low > high:
3        return -1
4
5    mid = low + (high - low) // 2
6
7    if arr[mid] == target:
8        return mid
9    if arr[mid] < target:
10        return binary_search_recursive(arr, target, mid + 1, high)
11    return binary_search_recursive(arr, target, low, mid - 1)
12
13items = [1, 3, 6, 8, 11, 15]
14print(binary_search_recursive(items, 8, 0, len(items) - 1))

Its recurrence is:

• T(n) = T(n / 2) + O(1)

Solving gives T(n) = O(log n), matching the halving intuition.

Preconditions and Practical Limits

Binary search is not universally correct. It depends on specific conditions.

• Data must be sorted according to the same comparison you use in search.
• Random access is important for performance, so arrays and vectors fit better than linked lists.
• Duplicate values require a policy if you need the first or last occurrence rather than any valid index.

For first occurrence, you continue searching left even after a match.

1def first_occurrence(arr, target):
2    low, high = 0, len(arr) - 1
3    ans = -1
4
5    while low <= high:
6        mid = low + (high - low) // 2
7        if arr[mid] >= target:
8            high = mid - 1
9        else:
10            low = mid + 1
11
12        if arr[mid] == target:
13            ans = mid
14
15    return ans

That still runs in O(log n).

Common Pitfalls

• Running binary search on unsorted input. Fix: Sort first or switch to linear search for one-off lookups.
• Off-by-one boundary errors in loop conditions. Fix: Use while low <= high and update bounds consistently.
• Midpoint overflow in languages with fixed integer width. Fix: Compute midpoint as low + (high - low) // 2.
• Assuming one match policy when duplicates exist. Fix: Implement first or last occurrence variants explicitly.
• Using binary search on linked lists and expecting O(log n). Fix: Use arrays or indexable structures for true logarithmic behavior.

Summary

• Binary search is divide-and-conquer because it halves the search space each step.
• Sorting lets it discard half the candidates after one comparison.
• The recurrence T(n) = T(n / 2) + O(1) yields O(log n) time.
• Iterative and recursive forms are both valid; iterative is often more practical.
• Correctness depends on sorted data, careful bounds handling, and duplicate-value policy.