C bsearch() Function

The bsearch() function in C is a standard library function that performs a binary search on a sorted array. It is part of the C standard library (stdlib.h). This function is useful for efficiently searching for a specific element in a sorted array.

Table of Contents

1. Introduction
2. bsearch() Function Syntax
3. Understanding bsearch() Function
4. Examples
   • Basic Usage of bsearch()
   • Searching for a Struct in an Array
5. Real-World Use Case
6. Conclusion

Introduction

The bsearch() function allows you to search for a specific element in a sorted array using the binary search algorithm. Binary search is an efficient algorithm with a time complexity of O(log n), making it suitable for searching large datasets.

bsearch() Function Syntax

The syntax for the bsearch() function is as follows:

void *bsearch(const void *key, const void *base, size_t nmemb, 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.
• nmemb: The number of elements in the array.
• size: The size of each element in the array.
• compar: A comparison function that compares two elements. It should return:
  • A negative value if the first element is less than the second.
  • Zero if the two elements are equal.
  • A positive value if the first element is greater than the second.

Returns:

• A pointer to the matching element in the array, or NULL if the element is not found.

Understanding bsearch() Function

The bsearch() function performs a binary search on a sorted array. The array must be sorted in ascending order based on the comparison function provided. The function returns a pointer to the found element or NULL if the element is not present in the array.

Examples

Basic Usage of bsearch()

To demonstrate how to use bsearch() to search for an integer in a sorted array, we will write a simple program.

Example

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

int compare_ints(const void *a, const void *b) {
    int int_a = *((int*)a);
    int int_b = *((int*)b);

    if (int_a < int_b) return -1;
    else if (int_a > int_b) return 1;
    else return 0;
}

int main() {
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int key = 5;
    int *item;
    size_t n = sizeof(array) / sizeof(array[0]);

    // Perform binary search
    item = (int*)bsearch(&key, array, n, sizeof(int), compare_ints);

    if (item != NULL) {
        printf("Found item: %d\n", *item);
    } else {
        printf("Item not found\n");
    }

    return 0;
}

Output:

Found item: 5

Searching for a Struct in an Array

This example shows how to use bsearch() to search for a struct in a sorted array of structs.

Example

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

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

int compare_persons(const void *a, const void *b) {
    Person *person_a = (Person*)a;
    Person *person_b = (Person*)b;

    return person_a->id - person_b->id;
}

int main() {
    Person people[] = {
        {1, "Alice"},
        {2, "Bob"},
        {3, "Charlie"},
        {4, "Diana"},
        {5, "Eve"}
    };
    Person key = {3, ""};  // We only need to set the key id
    Person *item;
    size_t n = sizeof(people) / sizeof(people[0]);

    // Perform binary search
    item = (Person*)bsearch(&key, people, n, sizeof(Person), compare_persons);

    if (item != NULL) {
        printf("Found person: %s\n", item->name);
    } else {
        printf("Person not found\n");
    }

    return 0;
}

Output:

Found person: Charlie

Real-World Use Case

Searching for Records in a Database

In real-world applications, bsearch() can be used to search for records in a sorted array or database efficiently. For example, you could use bsearch() to look up user information in a sorted array of user records.

Example: Searching for a User by ID

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

typedef struct {
    int user_id;
    char username[30];
} User;

int compare_users(const void *a, const void *b) {
    User *user_a = (User*)a;
    User *user_b = (User*)b;

    return user_a->user_id - user_b->user_id;
}

int main() {
    User users[] = {
        {101, "ramesh"},
        {102, "suresh"},
        {103, "mahesh"},
        {104, "naresh"},
        {105, "kalpesh"}
    };
    User key = {103, ""};  // We only need to set the key user_id
    User *item;
    size_t n = sizeof(users) / sizeof(users[0]);

    // Perform binary search
    item = (User*)bsearch(&key, users, n, sizeof(User), compare_users);

    if (item != NULL) {
        printf("Found user: %s\n", item->username);
    } else {
        printf("User not found\n");
    }

    return 0;
}

Output:

Found user: mahesh

Conclusion

The bsearch() function is used for performing binary searches on sorted arrays in C. By understanding and using this function correctly, you can efficiently search for elements in large datasets. Always ensure that the array is sorted and provide a proper comparison function to get accurate results.