LiveCodingInterview.com
← Articles

How to Implement Binary Search in C++

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

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

Prerequisites

  • Sorted container (vector, array, or any random-access sequence)
  • O(log n) search time

Template implementation

#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.

Generic template (interview bonus)

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;
}

STL: lower_bound and upper_bound

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 / upper_bound are essential for "first/last occurrence" and range-count problems.

Recursive version

int binarySearchRec(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 binarySearchRec(arr, x, lo, mid - 1);
    return binarySearchRec(arr, x, mid + 1, hi);
}

Binary search on the answer space

Interviewers often ask a variant that is not "search an array" but "search a range of possible answers" — minimum capacity to ship packages in D days, smallest divisor so a sum stays under a threshold, that kind of problem. The array is gone; you binary search over the space of possible answers using a monotonic predicate (a function that is false 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 — this is the "find the boundary" template, different from the classic find-exact-value template above. 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.

C++ interview tips

  • Prefer vector over raw arrays — size is tracked
  • Avoid arr[mid] with unsigned mid when hi can underflow — stick to signed int indices in the classic template
  • State complexity: O(log n) time, O(1) space (iterative)
  • When allowed, STL calls show library fluency; when asked to implement, use the while loop

Complexity

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