C binary search and the standard bsearch

Before you start

C arrays, pointers, and function pointers.

Find a value in a sorted array in logarithmic time, by hand and with the library function.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

#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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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

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) 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.