Tìm kiếm nhị phân trong mảng đã sắp xếp với bsearch() trong C

Trong lập trình C, tìm kiếm nhị phân là một phương pháp nhanh và hiệu quả để tìm một phần tử trong mảng đã sắp xếp. Hàm bsearch() trong thư viện chuẩn của C cung cấp một cách tiếp cận dễ dàng và tiện lợi để thực hiện tìm kiếm này.

Nguyên lý hoạt động của tìm kiếm nhị phân

Tìm kiếm nhị phân hoạt động bằng cách chia đôi mảng và kiểm tra phần tử ở giữa. Nếu phần tử này phù hợp, tìm kiếm kết thúc. Nếu không, tìm kiếm tiếp tục ở nửa bên trái nếu giá trị cần tìm nhỏ hơn, hoặc nửa bên phải nếu lớn hơn. Quá trình này lặp đi lặp lại cho đến khi tìm thấy phần tử hoặc khoảng tìm kiếm trở nên trống.

Cú pháp và cách sử dụng hàm bsearch()

Hàm bsearch() được định nghĩa trong <stdlib.h>, và cú pháp của nó như sau:

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

• key: Con trỏ đến phần tử cần tìm.
• base: Con trỏ đến mảng.
• nmemb: Số lượng phần tử trong mảng.
• size: Kích thước của mỗi phần tử.
• compar: Hàm so sánh được sử dụng để so sánh các phần tử.

Hàm so sánh

Hàm so sánh là một phần quan trọng trong bsearch(). Nó so sánh hai phần tử và trả về:

• Số âm nếu phần tử thứ nhất nhỏ hơn phần tử thứ hai.
• Số 0 nếu hai phần tử bằng nhau.
• Số dương nếu phần tử thứ nhất lớn hơn phần tử thứ hai.

Dưới đây là một ví dụ về hàm so sánh cho các số nguyên:

int compare_ints(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

Ví dụ cụ thể

Dưới đây là một ví dụ hoàn chỉnh về việc sử dụng bsearch() để tìm kiếm một số nguyên trong mảng đã sắp xếp:

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

int compare_ints(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int arr[] = {1, 2, 4, 5, 7, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int key = 5;

    // Sử dụng bsearch để tìm key trong arr
    int *item = (int *)bsearch(&key, arr, size, sizeof(int), compare_ints);

    if (item != NULL) {
        printf("Phần tử %d được tìm thấy tại vị trí: %ld\n", key, (item - arr));
    } else {
        printf("Phần tử %d không có trong mảng.\n", key);
    }

    return 0;
}

Phân tích ví dụ

1. Định nghĩa mảng và kích thước mảng: Mảng arr chứa các phần tử đã sắp xếp với kích thước được tính bằng sizeof.
2. Xác định giá trị cần tìm: Giá trị key được gán bằng 5.
3. Gọi hàm bsearch(): Hàm bsearch() được gọi với các tham số tương ứng để tìm kiếm key trong arr.
4. Kiểm tra kết quả: Nếu item không bằng NULL, tức là phần tử đã được tìm thấy và chúng ta in ra vị trí của nó. Ngược lại, thông báo rằng phần tử không có trong mảng.

Kết luận

Hàm bsearch() là một công cụ mạnh mẽ và tiện lợi để thực hiện tìm kiếm nhị phân trong mảng đã sắp xếp trong ngôn ngữ lập trình C. Bằng cách sử dụng hàm so sánh tùy chỉnh, bạn có thể áp dụng nó cho nhiều loại dữ liệu khác nhau, không chỉ là số nguyên mà còn cả chuỗi ký tự hoặc các cấu trúc phức tạp.

Hiểu rõ và vận dụng bsearch() sẽ giúp quá trình tìm kiếm dữ liệu trong mảng trở nên hiệu quả hơn, đặc biệt là khi làm việc với các tập dữ liệu lớn.