C: a sorted index and range queries with lower_bound
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).
C
#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;
}