C++UCS301
SearchingC++17

Binary Search

Binary search repeatedly halves an ordered search interval, reducing lookup from linear to logarithmic time.

Open this in the visual lab

What to understand

  • Sorted-data precondition
  • Safe midpoint calculation
  • Loop invariants
  • Iterative and recursive forms

Remember this

  1. 1The data must be sorted
  2. 2Use mid = low + (high-low)/2
  3. 3Decide whether bounds are inclusive
  4. 4O(log n) means very few comparisons

Detailed notes

Binary search maintains an interval that is guaranteed to contain the target if the target exists. Comparing the midpoint discards one half without inspecting it, which is valid only because the order makes that half impossible.

Both closed [low, high] and half-open [low, high) conventions work. Bugs arise when comparison branches, loop condition, and returned boundary mix different conventions.

How it works

  1. 1Confirm the range is sorted under the same comparator.
  2. 2Choose a closed or half-open interval invariant.
  3. 3Compute midpoint without overflow.
  4. 4Move a boundary past mid so the interval strictly shrinks.

Worked trace

Find 31 by halving

[4, 9, 13, 18, 25, 31, 42, 57]
  1. 1low=0, high=7, mid=3 → 18.
  2. 218 < 31, so low becomes 4.
  3. 3mid=(4+7)/2=5 → 31.
  4. 4The midpoint matches the target.
Result: Found at index 5 after two comparisons

Where it is used

  • Lookup in sorted arrays
  • Dictionary and index search
  • Core primitive behind boundary and answer-space searches

Common mistakes

  • Applying it to unsorted data
  • Setting low = mid instead of mid + 1
  • Overflow in (low + high) / 2

Complexity analysis

OperationBestAverageWorstExtra space
SearchO(1)O(log n)O(log n)O(1)

C++ implementation

C++17 reference
main.cpp

Iterative binary search

The inclusive interval [low, high] strictly shrinks on every iteration.

int binarySearch(const vector<int>& values, int target) {
    int low = 0, high = static_cast<int>(values.size()) - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (values[mid] == target) return mid;
        if (values[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
10 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.