Practice Now
C programming
lower_bound
algorithm implementation
coding
tutorial

Implementation of C lower_bound

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
AlgorithmsC & C++

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

c
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:

c
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:

c
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

c
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

cpp
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

python
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

c
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
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.