computer science · beginner · 10 min read · Updated Nov 7, 2026

Binary Search: Logarithmic Divide-and-Conquer Search

Understand the logarithmic efficiency of binary search, its strict sorted-array precondition, interval halving mechanics, and edge case implementations.

By Henrik Møller (Principal Systems Architect)

Learning Objectives

  • •
    State the strict precondition required before binary search can be applied.
  • •
    Trace the interval pointers (low, mid, high) across successive iterations.
  • •
    Explain why the time complexity of binary search is O(log n).
  • •
    Avoid the classic integer overflow bug when computing the middle index.
Binary search is the quintessential example of divide-and-conquer efficiency. In a sorted array of 1,000,000 items, while a linear scan might inspect every single element, binary search finds any target in at most 20 comparisons.

Why This Concept Matters

Searching is one of the most frequent operations executed by computers. Database B-Trees, Git bisect debugging, language runtime dictionaries, and routing lookups all rely directly on binary search principles to deliver sub-millisecond query responses.

Key Terminology

Sorted Precondition
The input sequence must be ordered (monotonically non-decreasing or non-increasing); without this, binary search produces incorrect results.
Search Space [low, high]
The contiguous sub-array interval where the target value could potentially reside.
Midpoint (mid)
The element at the center of the active search interval used to divide the remaining candidates in half.
Logarithmic Complexity
The property where doubling the input size only increases the total operations by 1 additional step.

1. The Divide-and-Conquer Paradigm

Imagine looking up a word in a physical dictionary with 1,000 pages. You do not start at page 1 and read word by word (that would be linear search, ). Instead, you open the book roughly in the middle. If your word alphabetically precedes the words on that page, you discard the entire right half of the book and repeat the procedure on the left half.
This is the essence of binary search: at each comparison, exactly half of the remaining elements are eliminated from consideration.
The Mandatory Precondition
Binary search requires that the array is already sorted. If the elements are unsorted, comparing the midpoint provides zero information about which half contains the target, leading to false negatives.

2. Pointer Halving Mechanics

The algorithm maintains two boundary pointers: low (beginning of active interval) and high (end of active interval). At each iteration, we compute the midpoint:

Calculating mid using low + (high - low) / 2 prevents integer overflow in languages with fixed-width integers (e.g. Java, C++).

  1. If array[mid] === target, search succeeds immediately and returns mid.
  2. If array[mid] < target, the target must reside in the upper half. We discard the left half by setting low = mid + 1.
  3. If array[mid] > target, the target must reside in the lower half. We discard the right half by setting high = mid - 1.
  4. If low > high, the search space has shrunk to zero elements. The target is not present.

3. Interactive Visual Execution Trace

Step through the execution of binary search on a sorted 10-element array. Observe how the active search space narrows by half on every step, and click different quick targets to test finding various indices or missing values.
Algorithm Trace

Interactive Binary Search on a Sorted Array

Interactive
Search Target: 23
Quick Targets:
LOW
MID
HIGH
2
[0]
5
[1]
8
[2]
12
[3]
16
[4]
23
[5]
38
[6]
56
[7]
72
[8]
91
[9]
Step 1 of 3 — Halving Search Space

array[4] = 16 < 23. Target must be in the right half. Adjusting low = mid + 1 (5).

low = 0 mid = ⌊(0+9)/2⌋ = 4 high = 9
Step 1 of 3
Use Next Step to watch pointers low, mid, and high adjust. Elements outside the active interval are dimmed out.

4. Canonical Implementation in TypeScript

typescript20 lines
export function binarySearch<T>(arr: T[], target: T): number {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    // Avoid (low + high) / 2 overflow in 32-bit environments
    const mid = low + Math.floor((high - low) / 2);
    const midVal = arr[mid];

    if (midVal === target) {
      return mid; // Target found
    } else if (midVal < target) {
      low = mid + 1; // Narrow to right half
    } else {
      high = mid - 1; // Narrow to left half
    }
  }

  return -1; // Target does not exist
}

Iterative implementation of binary search returning target index or -1.

5. Asymptotic Complexity Analysis

Because the search interval size is divided by 2 after each step (), the maximum number of iterations satisfies .
  • Best Case Time: — Occurs when the target happens to be located at the initial midpoint.
  • Average Case Time: — On random inputs, logarithmic comparisons are required.
  • Worst Case Time: — Occurs when the target is at the extreme ends or absent entirely.
  • Space Complexity: — The iterative implementation only stores two pointer variables, requiring constant auxiliary memory.

6. Check Your Understanding

Check Your Understanding
In the worst-case scenario, how many comparisons does binary search need to find an element in a sorted array of 1,024 items?
Flashcard Deck · quiz mode

Binary Search & Divide-and-Conquer Algorithms

Master interval halving mechanics, logarithmic recurrence relations, pointer boundaries, and real-world systems applications with spaced repetition.

Study Deck Quiz Mode
Cards →
Research & Foundations

Academic References & Verification

Foundational research, standard mathematical treatises, and verified peer-reviewed literature supporting this topic.

  1. Retrieval Practice Produces More Learning than Elaborative Studying with Concept Mapping

    Jeffrey D. Karpicke & Janell R. Blunt (2011). Science, 331(6018), 772–775.

    Demonstrates that retrieval practice outperforms elaborative concept mapping for conceptual retention and inferential problem solving.

    Does not imply concept mapping is without value; hierarchical mapping excels at organizing domain schemas, but active retrieval is required to retain them.

    doi:10.1126/science.1199327 Open access Primary source

Recommended Further Reading

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.

    The standard algorithms reference text with formal divide-and-conquer recurrences.

Related Learning Resources