C binary search and the standard bsearch

Find a value in a sorted array in logarithmic time, by hand and with the library function.

#include <stdio.h>
#include <stdlib.h>

static int binary_search(const int *a, int n, int key, int *steps) {
  int low = 0, high = n - 1;
  *steps = 0;
  while (low <= high) {
    (*steps)++;
    int mid = low + (high - low) / 2;
    if (a[mid] == key) {
      return mid;
    }
    if (a[mid] < key) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

static int compare_ints(const void *x, const void *y) {
  int a = *(const int *)x;
  int b = *(const int *)y;
  return (a > b) - (a < b);
}

int main(void) {
  int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
  int n = (int)(sizeof primes / sizeof primes[0]);
  int steps;

  int index = binary_search(primes, n, 11, &steps);
  printf("11: index %d in %d steps\n", index, steps);
  index = binary_search(primes, n, 4, &steps);
  printf("4: index %d in %d steps\n", index, steps);

  int key = 17;
  int *found = bsearch(&key, primes, (size_t)n, sizeof primes[0], compare_ints);
  printf("bsearch finds 17 at index %d\n", found ? (int)(found - primes) : -1);
  return 0;
}

Output

11: index 4 in 3 steps
4: index -1 in 3 steps
bsearch finds 17 at index 6

Explanation

Binary search works on a sorted array. It compares the target with the middle element and discards the half that cannot contain it, so a range of n elements needs at most about log2(n) + 1 comparisons. The middle is computed as low + (high - low) / 2, which cannot overflow, unlike (low + high) / 2.

The standard library offers bsearch in <stdlib.h>. It needs the array, its element count and size, the key, and a comparison function that returns negative, zero, or positive. It returns a pointer to the matching element or NULL, and subtracting the array's start from that pointer gives the index. The array must already be sorted by the same comparison.

Explore the dry run

Guided walkthroughReady

1#include <stdio.h>

2#include <stdlib.h>

4static int binary_search(const int *a, int n, int key, int *steps) {

5 int low = 0, high = n - 1;

6 *steps = 0;

7 while (low <= high) {

8 (*steps)++;

9 int mid = low + (high - low) / 2;

10 if (a[mid] == key) {

11 return mid;

12 }

13 if (a[mid] < key) {

14 low = mid + 1;

15 } else {

16 high = mid - 1;

17 }

18 }

19 return -1;

20}

22static int compare_ints(const void *x, const void *y) {

23 int a = *(const int *)x;

24 int b = *(const int *)y;

25 return (a > b) - (a < b);

26}

28int main(void) {

29 int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};

30 int n = (int)(sizeof primes / sizeof primes[0]);

31 int steps;

33 int index = binary_search(primes, n, 11, &steps);

34 printf("11: index %d in %d steps\n", index, steps);

35 index = binary_search(primes, n, 4, &steps);

36 printf("4: index %d in %d steps\n", index, steps);

38 int key = 17;

39 int *found = bsearch(&key, primes, (size_t)n, sizeof primes[0], compare_ints);

40 printf("bsearch finds 17 at index %d\n", found ? (int)(found - primes) : -1);

41 return 0;

42}

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
Look at the middle of the remaining range.	`—`	—
The key is larger than a[mid], so the left half and the middle are discarded.	`—`	—
Positions 3 (7), 5 (13), and 4 (11) are examined.	`—`	11: index 4 in 3 steps
4 is not in the array. The search ends after three comparisons with an empty range.	`—`	11: index 4 in 3 steps 4: index -1 in 3 steps
The library version uses a comparison function instead of ==.	`—`	11: index 4 in 3 steps 4: index -1 in 3 steps
Pointer subtraction converts the returned pointer to an index.	`—`	11: index 4 in 3 steps 4: index -1 in 3 steps bsearch finds 17 at index 6

Cost and common mistakes

O(log n) time and O(1) space.

Binary search on an unsorted array gives wrong answers without any error message.
(low + high) / 2 can overflow for very large arrays. The low + (high - low) / 2 form avoids that.
bsearch returns NULL when the key is missing. Check before dereferencing or subtracting.

Try it yourself

How many steps does the worst case need for 1,000,000 elements?

Reveal answer and reasoning

At most 20 steps, because 2^20 is just over a million.

C binary search and the standard bsearch

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading