C: a sorted index and range queries with lower_bound
Use binary search on a sorted array to find the first key at or above a value and read a range from there.
On this page
C arrays and binary search.
- Use binary search on a sorted array to find the first key at or above a value and read a range from there.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
A database index that keeps its keys sorted can answer range queries, such as all ages from 25 to 45, without reading every row. The key operation is lower_bound: the position of the first key that is greater than or equal to a value. It is found by binary search in O(log n).
To list the keys in [lo, hi], find lower_bound(lo) and lower_bound(hi + 1), and read everything between the two positions. The cost is O(log n) to find the start plus O(k) to read the k results. A B-tree stores the same sorted order in pages on disk, so the idea carries over to real databases.
Code example
#include <stdio.h>
static int lower_bound(const int *a, int n, int key) {
int lo = 0;
int hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < key) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
int main(void) {
int ages[] = {24, 29, 31, 45, 52, 60};
int n = (int)(sizeof ages / sizeof ages[0]);
int start = lower_bound(ages, n, 25);
int end = lower_bound(ages, n, 46);
printf("ages in [25, 45]:");
for (int i = start; i < end; i++) {
printf(" %d", ages[i]);
}
printf(" (%d rows)\n", end - start);
int first_over_50 = lower_bound(ages, n, 50);
printf("first age >= 50: %d\n", ages[first_over_50]);
return 0;
}ages in [25, 45]: 29 31 45 (3 rows) first age >= 50: 52
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
#include <stdio.h> static int lower_bound(const int *a, int n, int key) { int lo = 0; int hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < key) { lo = mid + 1; } else { hi = mid; } } return lo;} int main(void) { int ages[] = {24, 29, 31, 45, 52, 60}; int n = (int)(sizeof ages / sizeof ages[0]); int start = lower_bound(ages, n, 25); int end = lower_bound(ages, n, 46); printf("ages in [25, 45]:"); for (int i = start; i < end; i++) { printf(" %d", ages[i]); } printf(" (%d rows)\n", end - start); int first_over_50 = lower_bound(ages, n, 50); printf("first age >= 50: %d\n", ages[first_over_50]); return 0;}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The middle of the range, written so that lo + hi cannot overflow. | — | — | |
| If a[mid] is not smaller than the key, the answer is at mid or to its left. | — | — | |
| The first key above 45 marks where the range ends (exclusive). | — | — | |
| Positions 1 to 3 hold 29, 31, and 45. | — | ages in [25, 45]: 29 31 45 (3 rows) | |
| lower_bound(50) lands on 52, the first key that is at least 50. | — | ages in [25, 45]: 29 31 45 (3 rows) first age >= 50: 52 |
Behind the scenes
How C processes this code
The C compiler produces a native program. Variables occupy memory, and execution enters main.
Cost and common mistakes
O(log n) to locate the range plus O(k) to read k results.
- lower_bound can return n when every key is smaller. Check the position before reading ages[position].
- The array must stay sorted. Inserting in the middle costs O(n), which is why databases use trees for indexes that change often.
Try it yourself
What does lower_bound(ages, n, 100) return?
Reveal answer and reasoning
6, which is n: no key is at least 100, so the position is one past the last element.