Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c
binary search

What is bsearch() in C?

Kainat Asif

bsearch() is a standard C library function that uses the Binary search algorithm to find an element in an array. bsearch() is a part of the stdlib.h header file in C. Below is the declaration of the bsearch() function:

void* bsearch_s (const void *key, const void *base, rsize_t num, rsize_t size, int (*comparator)(const void *, const void *));

Parameters

  • key: Pointer to the element to be found in the array.
  • base: Pointer to the first element of the array.
  • num: Number of elements in the array.
  • size: Size (in bytes) of each element of the array.
  • comparator: Function that compares two elements of the array.

Return value

The bsearch() function returns the pointer to the key if the key is found in the array. If the key is not present in the array, a NULL pointer is returned.

Comparator

The comparator function is declared as follows:

int comparator (const void * num1, const void * num2);

The comparator function returns an integer by comparing num1 and num2 as follows:

  • Greater than 0: if the value pointed to by num1 is higher than the value pointed to by num2.
  • Equal to 0: if the value pointed to by num1 is equivalent to the value pointed to by num2.
  • Less than 0: if the value pointed to by num1 is lower than the value pointed to by num2.

Code

Consider the code snippet below, which uses bsearch() to find a key in an array:

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

int comparator (const void * num1, const void * num2) {
  return (*(int*)num1 - *(int*)num2);
}

void printArray(int arr[], int arrSize) {//function to print elements of an array
  for (int i=0; i<arrSize; i++) {
    printf("%d ", arr[i]);
  }
}

int main() {

  int arr[] = {1, 2, 9, 12, 56};
  int arrSize = 5;
  int key1 = 12;
  int key2 = 10;
  int * kPointer;

  printf("arr: ");
  printArray(arr, arrSize);
  printf("\n \n key1: %d \n", key1);
  
  kPointer = (int*) bsearch(&key1, arr, arrSize, sizeof(int), comparator);
  
  if( kPointer!=NULL ){
    printf(" key1: %d Found!! \n", *kPointer);
  }else{
    printf(" key1 not found!! \n");
  }

  printf("\n \n key2: %d \n", key2);
  
  kPointer = (int*) bsearch(&key2, arr, arrSize, sizeof(int), comparator);
  
  if( kPointer!=NULL ){
    printf(" key2: %d Found!! \n", *kPointer);
  }else{
    printf(" key2 not found!! \n");
  }
  

  
  return 0;
}

Explanation

The bsearch() function is used in lines 26 and 36 to find key1 and key2 in arr. As key1 is present in arr, bsearch() returns the pointer to key1. As key2 is not present in arr, bsearch() returns a NULL pointer.

RELATED TAGS

c
binary search

CONTRIBUTOR

Kainat Asif
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring