C Exercises: Binary Search using callback function

C Callback function: Exercise-11 with Solution

Write a program in C program to used to perform a binary search for an element in a sorted array using callback function.

Binary Search in C is a search algorithm used to search for an element in a sorted array.

In C language bsearch() function is used to perform a binary search of an array of num elements, each of size bytes. The array must be sorted ascendingly by the function pointed to by compare.

Sample Solution:

C Code:

#include <stdio.h>

#include <stdlib.h>

 // Define the type of the comparison function callback
typedef int( * compare_func_t)(const void * ,
  const void * );
// Implementation of the bsearch() function using a callback function
void * bsearch(const void * key,
  const void * base, size_t nmemb, size_t size, compare_func_t compare) {
  size_t left = 0, right = nmemb - 1;
  while (left <= right) {
    size_t mid = (left + right) / 2;
    int result = compare(key, (const char * ) base + mid * size);
    if (result < 0) {
      right = mid - 1;
    } else if (result > 0) {
      left = mid + 1;
    } else {
      return (void * )((const char * ) base + mid * size);
    }
  }
  return NULL;
}
// Example usage of the bsearch() function
int compare_ints(const void * a,
  const void * b) {
  const int * pa = (const int * ) a;
  const int * pb = (const int * ) b;
  return ( * pa > * pb) - ( * pa < * pb);
}
int main() {
  int arr[] = {
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    10
  };
  printf("Array elements: ");
  for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
    printf("%d ", arr[i]);
  }

  int key = 8;
  int * result = (int * ) bsearch( & key, arr, sizeof(arr) / sizeof(int), sizeof(int), compare_ints);
  if (result != NULL) {
    printf("\n%d found at index %ld\n", * result, result - arr);
  } else {
    printf("Could not find the number.", key);
  }
  return 0;
}

Sample Output:

Array elements: 1 2 3 4 5 6 7 8 9 10 
8 found at index 7  

Explanation:

In the above implementation of binary search, we use a callback function 'compare' to compare elements of the array base. The 'compare' function should take two const void* arguments, representing the elements to compare, and return an integer less than, equal to, or greater than zero if the first element is considered to be less than, equal to, or greater than the second element, respectively.

The bsearch() function takes a key to search for, an array base of nmemb elements, the size of each element size, and a compare callback function. It returns a pointer to the element in the array that matches the key, or NULL if no such element is found.

In the example usage of the bsearch() function, we search for the key value 8 in an array of integers using the compare_ints() function as the callback function. If the key is found, the function prints the value of the element and its index in the array otherwise prints "Could not find the number.".

Flowchart:

C Programming Code Editor:

Previous: Quick sort.