YouTipC Function Bsearch
# C Library Function - bsearch()
The `bsearch()` function is a standard C library function used to perform a binary search on a sorted array. It is defined in the `` header file.
Because it implements a binary search algorithm, the target array **must be sorted** in ascending order relative to the comparison function before calling `bsearch()`. The time complexity of this search is $O(\log n)$.
---
## Syntax
```c
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 target element you want to search for.
* **`base`**: A pointer to the first element of the array where the search will be performed.
* **`nmemb`**: The number of elements in the array.
* **`size`**: The size of each element in the array, in bytes (typically calculated using `sizeof`).
* **`compar`**: A pointer to the comparison function. This function defines how two elements are compared.
### Return Value
* If the target element is found, `bsearch()` returns a **pointer** to the matching element in the array.
* If the element is not found, it returns **`NULL`**.
* If there are multiple matching elements, the function may return a pointer to any one of them (not necessarily the first occurrence).
---
## The Comparison Function
The comparison function passed to `bsearch()` must match the following signature:
```c
int compar(const void *a, const void *b);
```
The function must compare the key (passed as the first argument `a`) with an array element (passed as the second argument `b`) and return an integer based on the comparison:
| Return Value | Description |
| :--- | :--- |
| **Negative value (`< 0`)** | The element pointed to by `a` is less than the element pointed to by `b`. |
| **Zero (`0`)** | The element pointed to by `a` is equal to the element pointed to by `b`. |
| **Positive value (`> 0`)** | The element pointed to by `a` is greater than the element pointed to by `b`. |
---
## Code Examples
### Example 1: Searching an Integer Array
The following example demonstrates how to use `bsearch()` to find an integer in a sorted array.
```c
#include
#include
// Comparison function for bsearch
int cmpfunc(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int values[] = { 5, 20, 29, 32, 63 };
int key = 32;
int *item;
// Calculate the number of elements in the array
size_t array_size = sizeof(values) / sizeof(values);
// Perform binary search for the value 32
item = (int*) bsearch(&key, values, array_size, sizeof(int), cmpfunc);
// Check and print the result
if (item != NULL) {
printf("Found item = %d\n", *item);
} else {
printf("Item = %d could not be found\n", key);
}
return 0;
}
```
#### Output
```text
Found item = 32
```
---
### Example 2: Searching an Array of Structures
`bsearch()` is highly versatile because it works with generic `void *` pointers. This allows you to search complex data structures, such as arrays of structs.
```c
#include
#include
#include
struct Student {
int id;
char name;
};
// Compare students by ID
int compare_students(const void *a, const void *b) {
struct Student *student_a = (struct Student *)a;
struct Student *student_b = (struct Student *)b;
return (student_a->id - student_b->id);
}
int main() {
// Sorted array of students by ID
struct Student database[] = {
{ 101, "Alice" },
{ 104, "Bob" },
{ 107, "Charlie" },
{ 110, "David" }
};
size_t size = sizeof(database) / sizeof(database);
// Search key (only the ID field needs to be populated for comparison)
struct Student search_key;
search_key.id = 107;
struct Student *result = (struct Student *)bsearch(
&search_key,
database,
size,
sizeof(struct Student),
compare_students
);
if (result != NULL) {
printf("Student found: ID = %d, Name = %s\n", result->id, result->name);
} else {
printf("Student with ID %d not found.\n", search_key.id);
}
return 0;
}
```
#### Output
```text
Student found: ID = 107, Name = Charlie
```
---
## Important Considerations
1. **Array Must Be Sorted**: The array must be sorted in ascending order according to the same comparison logic used by the `compar` function. If the array is not sorted, the behavior of `bsearch()` is undefined. You can use the standard library function `qsort()` to sort the array before searching.
2. **Pointer Arithmetic**: The return value is a generic pointer (`void *`). You must cast it back to the appropriate pointer type (e.g., `int *` or `struct Student *`) before dereferencing it.
3. **Integer Overflow Risk**: In the comparison function, subtracting two large integers (e.g., `*a - *b`) can cause integer overflow if one is highly positive and the other is highly negative. For maximum safety, use explicit comparison operators:
```c
int cmpfunc(const void *a, const void *b) {
int val_a = *(const int*)a;
int val_b = *(const int*)b;
if (val_a < val_b) return -1;
if (val_a > val_b) return 1;
return 0;
}
```