Thuật Toán Tìm Kiếm Nhị Phân Trong C — Ví Dụ Thực Tế

Bạn đã bao giờ thắc mắc tại sao tìm kiếm nhị phân trong C lại nhanh hơn hàng chục, thậm chí hàng nghìn lần so với cách tìm kiếm thông thường? Đây là một trong những thuật toán căn bản mà mọi sinh viên lập trình đều cần nắm vững. Trong bài này, bạn sẽ học cách thuật toán hoạt động, cách cài đặt bằng C (cả vòng lặp lẫn đệ quy), và thực hành qua các ví dụ có đầy đủ code chạy được.

Tìm Kiếm Nhị Phân Là Gì?

Tìm kiếm nhị phân (binary search) là thuật toán tìm kiếm một phần tử trong mảng đã được sắp xếp bằng cách liên tục chia đôi phạm vi tìm kiếm.

Ý tưởng cốt lõi:

• So sánh phần tử cần tìm với phần tử ở giữa mảng.
• Nếu bằng nhau → tìm thấy, dừng lại.
• Nếu nhỏ hơn → tiếp tục tìm ở nửa trái.
• Nếu lớn hơn → tiếp tục tìm ở nửa phải.
• Lặp lại cho đến khi tìm thấy hoặc phạm vi tìm kiếm rỗng.

So Sánh Với Tìm Kiếm Tuyến Tính

Với mảng 1.000.000 phần tử, tìm kiếm tuyến tính cần tối đa 1.000.000 bước, trong khi tìm kiếm nhị phân chỉ cần tối đa 20 bước (vì log₂(1.000.000) ≈ 20). Đây là lý do thuật toán này cực kỳ quan trọng trong thực tế.

Điều Kiện Áp Dụng Tìm Kiếm Nhị Phân

Trước khi sử dụng, bạn cần đảm bảo:

1. Mảng đã được sắp xếp (tăng dần hoặc giảm dần) — đây là điều kiện bắt buộc.
2. Bạn biết số lượng phần tử trong mảng.
3. Có thể truy cập phần tử theo chỉ số (random access) — mảng thông thường trong C đáp ứng điều này.

Nếu mảng chưa được sắp xếp, bạn cần sắp xếp trước bằng qsort() hoặc một thuật toán sắp xếp bất kỳ.

Cách Cài Đặt Tìm Kiếm Nhị Phân Trong C

Phiên Bản Vòng Lặp (Iterative)

Đây là cách cài đặt phổ biến nhất trong thực tế, dùng vòng lặp while để thu hẹp dần phạm vi tìm kiếm:

#include <stdio.h>

/* Hàm tìm kiếm nhị phân dùng vòng lặp
 * arr[] : mảng số nguyên đã sắp xếp tăng dần
 * n     : số phần tử trong mảng
 * target: giá trị cần tìm
 * Trả về: chỉ số của target, hoặc -1 nếu không tìm thấy
 */
int binarySearch(int arr[], int n, int target) {
    int left  = 0;       /* biên trái của phạm vi tìm kiếm */
    int right = n - 1;   /* biên phải của phạm vi tìm kiếm */

    while (left <= right) {
        /* Tính chỉ số giữa — cách này tránh tràn số so với (left+right)/2 */
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;           /* Tìm thấy: trả về vị trí */
        } else if (arr[mid] < target) {
            left = mid + 1;       /* target nằm ở nửa phải */
        } else {
            right = mid - 1;      /* target nằm ở nửa trái */
        }
    }

    return -1; /* Không tìm thấy */
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 67, 91};
    int n     = sizeof(arr) / sizeof(arr[0]);
    int target = 23;

    int result = binarySearch(arr, n, target);

    if (result != -1) {
        printf("Tim thay %d tai chi so %d\n", target, result);
    } else {
        printf("Khong tim thay %d trong mang\n", target);
    }

    return 0;
}

Tim thay 23 tai chi so 5

Lưu ý quan trọng: Luôn dùng mid = left + (right - left) / 2 thay vì (left + right) / 2. Khi left và right đều là số nguyên lớn, phép cộng left + right có thể gây tràn số nguyên (integer overflow) — một lỗi rất phổ biến trong lập trình thi đấu.

Phiên Bản Đệ Quy (Recursive)

Đệ quy (recursion) là kỹ thuật một hàm tự gọi lại chính nó với bài toán nhỏ hơn. Phiên bản này diễn đạt ý tưởng thuật toán một cách tự nhiên hơn:

#include <stdio.h>

/* Hàm tìm kiếm nhị phân đệ quy
 * Tìm target trong arr[left..right]
 */
int binarySearchRec(int arr[], int left, int right, int target) {
    /* Trường hợp cơ sở: phạm vi tìm kiếm rỗng */
    if (left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        /* Gọi đệ quy tìm trong nửa phải */
        return binarySearchRec(arr, mid + 1, right, target);
    } else {
        /* Gọi đệ quy tìm trong nửa trái */
        return binarySearchRec(arr, left, mid - 1, target);
    }
}

int main() {
    int arr[] = {1, 3, 7, 15, 22, 34, 49, 58, 73, 99};
    int n     = sizeof(arr) / sizeof(arr[0]);
    int target = 49;

    int result = binarySearchRec(arr, 0, n - 1, target);

    if (result != -1) {
        printf("Tim thay %d tai chi so %d\n", target, result);
    } else {
        printf("Khong tim thay %d\n", target);
    }

    return 0;
}

Tim thay 49 tai chi so 6

Trong thực tế, phiên bản vòng lặp được ưu tiên hơn vì nó tránh được lỗi tràn stack (stack overflow) khi mảng rất lớn. Phiên bản đệ quy hữu ích hơn cho việc học và hiểu thuật toán.

Ví Dụ Thực Tế — Tra Cứu Mã Sinh Viên

Giả sử bạn có danh sách mã sinh viên đã sắp xếp và cần tra cứu nhanh xem một mã có tồn tại không:

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

/* Tìm kiếm nhị phân trên mảng chuỗi ký tự */
int searchStudentID(char ids[][20], int n, const char *target) {
    int left = 0, right = n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        /* strcmp trả về 0 nếu bằng nhau, <0 nếu ids[mid] < target */
        int cmp = strcmp(ids[mid], target);

        if (cmp == 0) {
            return mid;           /* Tìm thấy mã sinh viên */
        } else if (cmp < 0) {
            left = mid + 1;       /* Tìm nửa sau */
        } else {
            right = mid - 1;      /* Tìm nửa trước */
        }
    }

    return -1; /* Không tìm thấy */
}

int main() {
    /* Danh sách mã sinh viên đã sắp xếp theo bảng chữ cái */
    char ids[6][20] = {"SV001", "SV002", "SV010", "SV025", "SV042", "SV099"};
    int n = 6;

    const char *query = "SV025";
    int idx = searchStudentID(ids, n, query);

    if (idx != -1) {
        printf("Ma %s duoc tim thay tai vi tri chi so %d\n", query, idx);
    } else {
        printf("Khong tim thay ma %s\n", query);
    }

    return 0;
}

Ma SV025 duoc tim thay tai vi tri chi so 3

Bài Tập Luyện Tập

Hãy tự giải các bài sau để củng cố kiến thức:

Bài 1 — Cơ bản: Nhập mảng n số nguyên từ bàn phím, sắp xếp tăng dần bằng qsort(), rồi dùng tìm kiếm nhị phân để tìm một giá trị k do người dùng nhập vào.

Bài 2 — Biến thể: Viết hàm tìm lần xuất hiện đầu tiên của một phần tử trong mảng có thể có phần tử trùng lặp. Ví dụ: {1, 2, 2, 2, 3}, tìm 2 → trả về chỉ số 1, không phải 2 hay 3.

Bài 3 — Nâng cao: Dùng tìm kiếm nhị phân để tính căn bậc hai nguyên của một số n — tức là số nguyên lớn nhất x sao cho x * x <= n. Ví dụ: n = 17 → kết quả là 4.

Kết Luận

Dưới đây là những điểm quan trọng nhất về tìm kiếm nhị phân trong C mà bạn cần ghi nhớ:

• Điều kiện tiên quyết: mảng phải được sắp xếp — đây là điều bắt buộc, không có ngoại lệ.
• Hiệu suất vượt trội: O(log n) nhanh hơn rất nhiều so với O(n) khi dữ liệu lớn.
• Hai cách cài đặt: vòng lặp (an toàn hơn, dùng trong thực tế) và đệ quy (dễ hiểu hơn về mặt tư duy).
• Tránh lỗi tràn số: luôn tính mid = left + (right - left) / 2.
• Ứng dụng rộng: tìm kiếm nhị phân không chỉ dùng trên mảng số — bạn có thể áp dụng cho chuỗi, đối tượng, và cả các bài toán tối ưu hóa kiểu “binary search on answer”.

Hãy tự mình gõ lại toàn bộ code, biên dịch, chạy thử với nhiều bộ dữ liệu khác nhau, và giải từng bài tập ở trên. Hiểu thuật toán qua lý thuyết là tốt, nhưng thực hành mới là con đường duy nhất để thực sự thành thạo lập trình! ```

Summary:

Summary: