Introduction
lower_bound is a binary search algorithm that finds the first position in a sorted array where a value could be inserted without breaking the sort order. In C++ STL, it returns an iterator to the first element that is not less than the target value. C does not have this function built in, but it can be implemented with a simple binary search loop. The algorithm runs in O(log n) time and is fundamental for range queries, sorted insertions, and counting elements in sorted arrays.
C Implementation
1#include <stdio.h>
2
3// Returns the index of the first element >= value
4// If all elements are less than value, returns n (past the end)
5int lower_bound(int arr[], int n, int value) {
6 int lo = 0, hi = n;
7
8 while (lo < hi) {
9 int mid = lo + (hi - lo) / 2;
10
11 if (arr[mid] < value) {
12 lo = mid + 1;
13 } else {
14 hi = mid;
15 }
16 }
17
18 return lo;
19}
20
21int main() {
22 int arr[] = {1, 3, 3, 5, 7, 9, 11};
23 int n = sizeof(arr) / sizeof(arr[0]);
24
25 printf("lower_bound(3) = %d\n", lower_bound(arr, n, 3)); // 1
26 printf("lower_bound(4) = %d\n", lower_bound(arr, n, 4)); // 3
27 printf("lower_bound(5) = %d\n", lower_bound(arr, n, 5)); // 3
28 printf("lower_bound(12) = %d\n", lower_bound(arr, n, 12)); // 7 (past end)
29 printf("lower_bound(0) = %d\n", lower_bound(arr, n, 0)); // 0
30
31 return 0;
32}
The key insight is that lo always converges to the first index where arr[index] >= value.
Upper Bound Implementation
upper_bound finds the first element strictly greater than the value:
1// Returns the index of the first element > value
2int upper_bound(int arr[], int n, int value) {
3 int lo = 0, hi = n;
4
5 while (lo < hi) {
6 int mid = lo + (hi - lo) / 2;
7
8 if (arr[mid] <= value) { // Only difference: <= instead of <
9 lo = mid + 1;
10 } else {
11 hi = mid;
12 }
13 }
14
15 return lo;
16}
17
18// arr = {1, 3, 3, 5, 7}
19// upper_bound(3) = 3 (index of first element > 3, which is 5)
20// lower_bound(3) = 1 (index of first element >= 3, which is 3)
Counting Occurrences in a Sorted Array
Combine lower_bound and upper_bound to count how many times a value appears:
1int count_occurrences(int arr[], int n, int value) {
2 return upper_bound(arr, n, value) - lower_bound(arr, n, value);
3}
4
5// arr = {1, 3, 3, 3, 5, 7}
6// count_occurrences(3) = upper_bound(3) - lower_bound(3) = 4 - 1 = 3
Generic Implementation with Comparators
1#include <stddef.h>
2
3// Generic lower_bound using void pointers and comparator
4size_t lower_bound_generic(
5 const void *arr,
6 size_t count,
7 size_t elem_size,
8 const void *value,
9 int (*cmp)(const void *, const void *)
10) {
11 size_t lo = 0, hi = count;
12
13 while (lo < hi) {
14 size_t mid = lo + (hi - lo) / 2;
15 const void *mid_elem = (const char *)arr + mid * elem_size;
16
17 if (cmp(mid_elem, value) < 0) {
18 lo = mid + 1;
19 } else {
20 hi = mid;
21 }
22 }
23
24 return lo;
25}
26
27// Comparator for integers
28int int_cmp(const void *a, const void *b) {
29 return (*(const int *)a) - (*(const int *)b);
30}
31
32// Usage
33int arr[] = {1, 3, 5, 7, 9};
34int target = 5;
35size_t idx = lower_bound_generic(arr, 5, sizeof(int), &target, int_cmp);
36// idx = 2
C++ STL Reference
1#include <algorithm>
2#include <vector>
3#include <iostream>
4
5int main() {
6 std::vector<int> v = {1, 3, 3, 5, 7, 9};
7
8 // lower_bound: first element >= 3
9 auto lb = std::lower_bound(v.begin(), v.end(), 3);
10 std::cout << "lower_bound(3): index " << (lb - v.begin()) << std::endl; // 1
11
12 // upper_bound: first element > 3
13 auto ub = std::upper_bound(v.begin(), v.end(), 3);
14 std::cout << "upper_bound(3): index " << (ub - v.begin()) << std::endl; // 3
15
16 // Count of 3s
17 std::cout << "count of 3: " << (ub - lb) << std::endl; // 2
18
19 // equal_range: returns (lower_bound, upper_bound) as a pair
20 auto [first, last] = std::equal_range(v.begin(), v.end(), 3);
21 std::cout << "range: [" << (first - v.begin()) << ", "
22 << (last - v.begin()) << ")" << std::endl; // [1, 3)
23
24 return 0;
25}
Python Equivalent
1import bisect
2
3arr = [1, 3, 3, 5, 7, 9]
4
5# lower_bound equivalent
6idx = bisect.bisect_left(arr, 3) # 1
7
8# upper_bound equivalent
9idx = bisect.bisect_right(arr, 3) # 3
10
11# Count occurrences
12count = bisect.bisect_right(arr, 3) - bisect.bisect_left(arr, 3) # 2
13
14# Insert maintaining sort order
15bisect.insort_left(arr, 4) # arr = [1, 3, 3, 4, 5, 7, 9]
Use Cases
1// 1. Find insertion point in sorted array
2int insert_pos = lower_bound(arr, n, new_value);
3
4// 2. Check if value exists
5int idx = lower_bound(arr, n, value);
6int exists = (idx < n && arr[idx] == value);
7
8// 3. Find first element >= threshold
9int idx = lower_bound(arr, n, threshold);
10if (idx < n) {
11 printf("First element >= %d is %d\n", threshold, arr[idx]);
12}
13
14// 4. Count elements in range [lo_val, hi_val]
15int count = lower_bound(arr, n, hi_val + 1) - lower_bound(arr, n, lo_val);
Common Pitfalls
Integer overflow in midpoint calculation: (lo + hi) / 2 overflows for large values of lo and hi. Always use lo + (hi - lo) / 2 to compute the midpoint safely.
Array must be sorted: lower_bound assumes the array is sorted in ascending order. Using it on an unsorted array produces incorrect results. Sort the array first with qsort or ensure it is maintained in sorted order.
Off-by-one with the return value: lower_bound returns n (one past the last element) when the value is greater than all elements. Always check idx < n before accessing arr[idx] to avoid out-of-bounds access.
Confusing lower_bound and upper_bound: lower_bound returns the first position where arr[pos] >= value. upper_bound returns the first position where arr[pos] > value. For counting occurrences of value, you need both.
Using <= instead of < in the comparison: The loop condition uses lo < hi, not lo <= hi. Using <= causes an infinite loop when lo == hi because the search space never shrinks to empty.
Summary
lower_bound finds the first index where arr[index] >= value using binary search in O(log n)
The implementation uses lo and hi pointers with lo < hi as the loop condition
upper_bound is identical but uses <= in the comparison instead of <
Combine both to count occurrences: upper_bound(v) - lower_bound(v)
Use lo + (hi - lo) / 2 for safe midpoint calculation
In C++, use std::lower_bound; in Python, use bisect.bisect_left
