bsearch() Function

The bsearch() function is declared in the header file <stdlib.h>.

The bsearch() function performs a binary search on a sorted array, efficiently locating a specified key. It uses a user-defined comparison function to determine the order of elements and to identify a matching element.

Syntax of bsearch()

</>
Copy
void *bsearch(const void *key, const void *base, size_t num, size_t size, int (*compar)(const void*, const void*));

Parameters

ParameterDescription
keyPointer to the object that serves as the search key (cast to void*).
basePointer to the first element of the sorted array in which to perform the search.
numNumber of elements in the array.
sizeSize in bytes of each element in the array.
comparPointer to the comparison function used to compare the search key with array elements.

The comparison function should return a negative value if the key is less than the element, zero if they are equal, and a positive value if the key is greater. The array must be sorted in accordance with the same criteria used by the comparison function.

Return Value

The function returns a pointer to a matching element in the array if found. If multiple elements match, any matching element may be returned. If no match is found, a null pointer is returned.

Examples for bsearch()

Example 1: Searching for an Integer in a Sorted Array

This example demonstrates how to use bsearch() to locate an integer in a sorted array.

Program

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

int compareInt(const void *a, const void *b) {
    int int_a = *(const int *)a;
    int int_b = *(const int *)b;
    if (int_a < int_b) return -1;
    if (int_a > int_b) return 1;
    return 0;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14};
    int key = 8;
    int *found;

    found = (int *)bsearch(&key, arr, 7, sizeof(int), compareInt);
    if (found != NULL) {
        printf("Found %d in the array.\n", *found);
    } else {
        printf("Key not found in the array.\n");
    }
    return 0;
}

Explanation:

  1. A sorted array of integers is defined.
  2. The compareInt function compares two integers.
  3. bsearch() is called with the address of the key, the array, number of elements, size of each element, and the comparison function.
  4. If the key is found, the corresponding element is printed; otherwise, a not-found message is displayed.

Program Output:

Found 8 in the array.

Example 2: Searching for a String in a Sorted Array of Strings

This example demonstrates how to use bsearch() to locate a string in a sorted array of strings.

Program

</>
Copy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compareString(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

int main() {
    const char *arr[] = {"apple", "banana", "cherry", "date", "fig"};
    const char *key = "cherry";
    char **found;

    found = (char **)bsearch(&key, arr, 5, sizeof(const char *), compareString);
    if (found != NULL) {
        printf("Found %s in the array.\n", *found);
    } else {
        printf("Key not found in the array.\n");
    }
    return 0;
}

Explanation:

  1. A sorted array of string literals is defined.
  2. The compareString function compares two strings using strcmp().
  3. bsearch() is invoked with the search key, array, number of elements, size of each element, and the comparison function.
  4. If the key is found, the corresponding string is printed; otherwise, a not-found message is displayed.

Program Output:

Found cherry in the array.

Example 3: Searching for a Structure in an Array

This example illustrates how to use bsearch() to locate a structure within an array of structures.

Program

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

typedef struct {
    int id;
    char name[20];
} Person;

int comparePerson(const void *a, const void *b) {
    const Person *p1 = (const Person *)a;
    const Person *p2 = (const Person *)b;
    return (p1->id - p2->id);
}

int main() {
    Person people[] = {
        {101, "Alice"},
        {102, "Bob"},
        {103, "Charlie"}
    };
    Person key = {102, ""};
    Person *found;

    found = (Person *)bsearch(&key, people, 3, sizeof(Person), comparePerson);
    if (found != NULL) {
        printf("Found Person: ID = %d, Name = %s\n", found->id, found->name);
    } else {
        printf("Person not found in the array.\n");
    }
    return 0;
}

Explanation:

  1. An array of Person structures is defined and sorted by the id field.
  2. The comparePerson function compares the id of two Person structures.
  3. bsearch() is used to search for a person with a specific id.
  4. If a matching structure is found, the person’s details are printed; otherwise, a not-found message is displayed.

Program Output:

Found Person: ID = 102, Name = Bob