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.

#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;
}

Output

ages in [25, 45]: 29 31 45 (3 rows)
first age >= 50: 52

Explanation

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.

Explore the dry run

Guided walkthroughReady

1#include <stdio.h>

3static int lower_bound(const int *a, int n, int key) {

4 int lo = 0;

5 int hi = n;

6 while (lo < hi) {

7 int mid = lo + (hi - lo) / 2;

8 if (a[mid] < key) {

9 lo = mid + 1;

10 } else {

11 hi = mid;

12 }

13 }

14 return lo;

15}

17int main(void) {

18 int ages[] = {24, 29, 31, 45, 52, 60};

19 int n = (int)(sizeof ages / sizeof ages[0]);

21 int start = lower_bound(ages, n, 25);

22 int end = lower_bound(ages, n, 46);

23 printf("ages in [25, 45]:");

24 for (int i = start; i < end; i++) {

25 printf(" %d", ages[i]);

26 }

27 printf(" (%d rows)\n", end - start);

29 int first_over_50 = lower_bound(ages, n, 50);

30 printf("first age >= 50: %d\n", ages[first_over_50]);

31 return 0;

32}

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

Prepared trace of the published program. Some rows group repeated iterations.
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

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.

C: a sorted index and range queries with lower_bound

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading