bsearch() function in C++

In this guide, you will learn what is bsearch() function is in C++ programming and how to use it with an example.

1. bsearch() Function Overview

The bsearch() function, part of the C standard library <cstdlib> in C++, provides a way to search for an element in a sorted array using the binary search algorithm. It returns a pointer to the matching element if found, or NULL if the element is not present.

Signature:

void* bsearch(const void* key, const void* base, size_t nitems, size_t size, int (*compar)(const void*, const void*));

Parameters:

- key: A pointer to the element you are searching for.

- base: A pointer to the first element of the array.

- nitems: The number of elements in the array.

- size: The size in bytes of each element in the array.

- compar: A function pointer to the comparison function which determines the order of elements.

2. Source Code Example

#include <iostream>
#include <cstdlib>

// Comparison function
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int values[] = {10, 20, 25, 40, 90, 100};
    int key = 25;

    // Number of elements in the array
    int n = sizeof(values) / sizeof(values[0]);

    // Using bsearch to find the key in the array
    int* found = (int*) bsearch(&key, values, n, sizeof(int), compare);

    if(found) {
        std::cout << key << " found at index " << (found - values) << std::endl;
    } else {
        std::cout << key << " not found in the array." << std::endl;
    }

    return 0;
}

Output:

25 found at index 2

3. Explanation

1. We define a comparison function compare(). This function takes two void pointers as arguments, which point to the elements being compared. Inside the function, these pointers are cast to the appropriate data type (int* in this case) and used for comparison.

2. In the main() function, we have a sorted integer array values in which we want to find the key.

3. We use the bsearch() function, providing the necessary parameters like the key we're searching for, the base address of the array, the number of items, the size of each item, and the comparison function.

4. If the element is found, bsearch() returns a pointer to it. We calculate its index in the array by subtracting the base address from the returned pointer. If the element is not found, bsearch() returns NULL.

Note: For bsearch() to work correctly, the array should be sorted in the order defined by the comparison function.