LiveCodingInterview.com
← Articles

How to Implement Binary Search in C++

C++ interviews often expect comfort with both raw loops and the STL algorithms `<algorithm>`. 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);
}

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