LiveCodingInterview.com
← Articles

How to Implement Binary Search in C++

C++ interviews often expect comfort with both raw loops and the STL algorithms library, and binary search on sorted data is O(log n) either way, so know both styles.

Start with the full concept guide: Binary Search Algorithm: A Coding Interview Guide.

What Do You Need Before Binary Search Works?

  • A sorted container (vector, array, or any random-access sequence)
  • A monotonic condition so the search space can be cut in half every step

How Do You Implement the Classic Binary Search Template?

#include <vector>

int binarySearch(const std::vector<int>& arr, int x) {
    int lo = 0;
    int hi = static_cast<int>(arr.size()) - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}

Cast arr.size() to int when mixing with signed indices, or use size_t consistently with care at boundaries.

How Do You Write a Generic Template for Any Type?

template<typename T>
int binarySearch(const std::vector<T>& arr, const T& x) {
    int lo = 0, hi = static_cast<int>(arr.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

Interviewers give partial credit for recognizing that the comparison, not the container type, is what needs to generalize.

How Do You Implement Binary Search Recursively?

Interviewers occasionally ask for the recursive version specifically, usually to check whether you can reason about the stack depth it adds:

int binarySearchRecursive(const std::vector<int>& arr, int x, int lo, int hi) {
    if (lo > hi) return -1;

    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearchRecursive(arr, x, lo, mid - 1);
    return binarySearchRecursive(arr, x, mid + 1, hi);
}

int binarySearchRecursive(const std::vector<int>& arr, int x) {
    return binarySearchRecursive(arr, x, 0, static_cast<int>(arr.size()) - 1);
}

Same O(log n) time as the iterative version, but O(log n) space instead of O(1), since each recursive call adds a stack frame until the base case returns. Say this out loud if asked to pick one: prefer the iterative version in an interview unless the interviewer specifically wants the recursive structure, since it's the safer default under time pressure and costs nothing extra.

What Do lower_bound and upper_bound Do in the STL?

The C++ standard library implements binary search in O(log n):

#include <algorithm>
#include <vector>

std::vector<int> arr = {1, 3, 5, 5, 7, 9};
int x = 5;

// First element >= x
auto it = std::lower_bound(arr.begin(), arr.end(), x);
bool found = it != arr.end() && *it == x;
int idx = static_cast<int>(it - arr.begin());

// First element > x
auto it2 = std::upper_bound(arr.begin(), arr.end(), x);

// std::binary_search returns bool only
bool exists = std::binary_search(arr.begin(), arr.end(), x);

lower_bound finds the first position where x could be inserted without breaking order, upper_bound finds the position just past the last equal element, and the gap between the two indices is the count of x in the container. That pairing is essential for "first/last occurrence" and range-count problems, and citing it by name signals real STL fluency rather than a memorized loop. The STL also gives you both calls in one: std::equal_range(arr.begin(), arr.end(), x) returns a std::pair of the same two iterators in a single O(log n) call, which is the more idiomatic choice when you need both bounds and don't already have one of them from a prior lookup.

How Do You Find the First and Last Occurrence of a Duplicate Value?

This is one of the most common C++-flavored binary search questions, precisely because lower_bound and upper_bound solve it in two lines instead of a hand-rolled loop:

#include <algorithm>
#include <vector>

std::pair<int, int> firstAndLastOccurrence(const std::vector<int>& arr, int x) {
    auto lo = std::lower_bound(arr.begin(), arr.end(), x);
    if (lo == arr.end() || *lo != x) return {-1, -1};

    auto hi = std::upper_bound(arr.begin(), arr.end(), x) - 1;
    return {
        static_cast<int>(lo - arr.begin()),
        static_cast<int>(hi - arr.begin())
    };
}

Say out loud why this is still O(log n): two binary searches back to back is still logarithmic, since dropping the constant factor is exactly what Big O asks you to do.

How Do You Search a Rotated Sorted Array?

A sorted array rotated at an unknown pivot is the classic twist on plain binary search. At every step, one half of the array (split by mid) is still sorted, so check which half that is and decide whether the target could be in it:

int searchRotated(const std::vector<int>& arr, int target) {
    int lo = 0, hi = static_cast<int>(arr.size()) - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;

        if (arr[lo] <= arr[mid]) {
            // Left half is sorted
            if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            // Right half is sorted
            if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

The signal to listen for is "rotated sorted array" in the prompt. The moment you hear it, say out loud that one half around mid is always sorted, then decide which half to search based on where the target falls relative to that sorted half.

How Do You Search a 2D Matrix in O(log(mn)) Time?

When a matrix is sorted row by row and each row's first value exceeds the previous row's last value, treat the whole grid as one sorted array and map a single index back to a row and column:

bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;
    int rows = static_cast<int>(matrix.size());
    int cols = static_cast<int>(matrix[0].size());
    int lo = 0, hi = rows * cols - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = matrix[mid / cols][mid % cols];
        if (val == target) return true;
        if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

Naming this "binary search on a flattened matrix" up front tells the interviewer you spotted the O(log(mn)) approach instead of the O(m + n) staircase search some candidates default to.

How Do You Binary Search Over a Range of Possible Answers?

Interviewers often ask a variant that is not "search an array" but "search a range of possible answers," such as the minimum capacity to ship packages in D days, or the smallest divisor so a sum stays under a threshold. The array is gone, and instead you binary search over the space of possible answers using a monotonic predicate, a function that is false and then true as the answer increases.

#include <vector>

// Example predicate: "can we finish with capacity mid?" (replace with your problem's check)
bool canFinish(const std::vector<int>& weights, int days, int capacity) {
    int daysNeeded = 1;
    int load = 0;
    for (int w : weights) {
        if (load + w > capacity) {
            daysNeeded++;
            load = 0;
        }
        load += w;
    }
    return daysNeeded <= days;
}

int minCapacity(const std::vector<int>& weights, int days) {
    int lo = *std::max_element(weights.begin(), weights.end());
    int hi = 0;
    for (int w : weights) hi += w;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(weights, days, mid)) {
            hi = mid;      // mid works, try smaller
        } else {
            lo = mid + 1;  // mid fails, need bigger
        }
    }
    return lo;
}

Note the loop condition is lo < hi, not lo <= hi. That is the "find the boundary" template, different from the classic find-exact-value template above, and lo converges to the smallest value where the predicate is true. Recognize the shape: no sorted array in sight, but the answer space is monotonic, so binary search still applies in O(log(range)) time. LeetCode patterns worth recognizing on sight covers this "search on the answer" signal alongside the other patterns that trip candidates up.

What Should You Watch for in a C++ Binary Search Interview?

  • Prefer vector over raw arrays, since size is tracked automatically instead of passed around separately
  • Avoid arr[mid] with an unsigned mid when hi can underflow; stick to signed int indices in the classic template
  • State complexity out loud: O(log n) time, O(1) space for the iterative version
  • When allowed, naming the STL call shows library fluency, and when asked to implement it by hand, fall back to the while loop

Complexity

  • Time: O(log n)
  • Space: O(1) iterative, O(log n) recursive

Frequently Asked Questions

Is std::binary_search enough, or should I know the manual version?

Know both, since std::binary_search only returns a bool and cannot tell you where the value is or which duplicate you found. Interviewers usually want the manual while loop first, then a mention that the STL versions exist for production code.

What is the actual difference between lower_bound and upper_bound?

lower_bound returns an iterator to the first element not less than the target, so it points at the target itself when the target exists. upper_bound returns an iterator to the first element strictly greater than the target, landing one past the last occurrence. Subtracting the two iterators gives the count of the target in the range.

Why does my binary search loop forever in C++?

Almost always because hi is set to mid instead of mid - 1 (or lo to mid instead of mid + 1) inside a lo <= hi loop, so the range never shrinks on that branch. The "search on the answer" template intentionally uses lo < hi with hi = mid to avoid this trap; mixing the two templates is the most common source of infinite loops.

Does mid = lo + (hi - lo) / 2 actually matter over (lo + hi) / 2 in C++?

Yes, for very large indices, since (lo + hi) / 2 can overflow a signed int before the division happens if lo and hi are both close to INT_MAX, and undefined behavior on signed overflow is a real bug, not just a style nitpick. lo + (hi - lo) / 2 never lets the intermediate sum exceed hi.