6.19.13 bsearch Function

Performs a binary search.

Include

<stdlib.h>

Prototype

void *bsearch(const void *key, const void *base, size_t nelem, size_t size, int (*cmp)(const void *ck, const void *ce));

Arguments

key

object to search for

base

pointer to the start of the search data

nelem

number of elements

size

size of elements

cmp

pointer to the comparison function

Arguments to the comparison function are as follows.

ck

pointer to the key for the search

ce

pointer to the element being compared with the key

Return Value

Returns a pointer to the object being searched for if found; otherwise, returns NULL.

Remarks

The value returned by the compare function is <0 if ck is less than ce, 0 if ck is equal to ce or >0 if ck is greater than ce.

In the following example, qsort is used to sort the list before bsearch is called. bsearch requires the list to be sorted according to the comparison function. This comp uses ascending order.

Example

See the notes at the beginning of this chapter or section for information on using printf() or scanf() (and other functions reading and writing the stdin or stdout streams) in the example code.

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

#define NUM 7

int comp(const void *e1, const void *e2);

int main(void)
{
  int list[NUM] = {35, 47, 63, 25, 93, 16, 52};
  int x, y;
  int *r;

  qsort(list, NUM, sizeof(int), comp);

  printf("Sorted List:   ");
  for (x = 0; x < NUM; x++)
    printf("%d  ", list[x]);

  y = 25;
  r = bsearch(&y, list, NUM, sizeof(int), comp);
  if (r)
    printf("\nThe value %d was found\n", y);
  else
    printf("\nThe value %d was not found\n", y);

  y = 75;
  r = bsearch(&y, list, NUM, sizeof(int), comp);
  if (r)
    printf("\nThe value %d was found\n", y);
  else
    printf("\nThe value %d was not found\n", y);
}

int comp(const void *e1, const void *e2)
{

  const int * a1 = e1;
  const int * a2 = e2;
 
  if (*a1 < *a2)
    return -1;
  else if (*a1 == *a2)
    return 0;
  else
    return 1;
}

Example Output

Sorted List:   16  25  35  47  52  63  93
The value 25 was found

The value 75 was not found