Tìm kiếm nhị phân (Binary Search) đệ quy và lặp trong C

Tìm kiếm nhị phân (Binary Search) là thuật toán tìm vị trí phần tử (giá trị mục tiêu) trong mảng đã sắp xếp. Mảng phải được sắp xếp trước khi áp dụng.

Còn gọi là: tìm kiếm logarit, binary chop, tìm kiếm khoảng nửa.

Cách hoạt động

So sánh phần tử cần tìm với phần tử giữa mảng:

• Trường hợp 1: phần tử = giữa → tìm thấy, trả về chỉ số.
• Trường hợp 2: phần tử > giữa → tìm trong nửa phải (middle+1 đến n).
• Trường hợp 3: phần tử < giữa → tìm trong nửa trái (0 đến middle-1).

Thuật toán

Tham số: start_index, end_index
B1: Tìm phần tử giữa: middle = start + (end - start) / 2
B2: Nếu middle == phần tử → trả về "tìm thấy" và chỉ số
B3: Nếu middle > phần tử → gọi lại với end = middle - 1
B4: Nếu middle < phần tử → gọi lại với start = middle + 1
B5: Kết thúc

Có hai cách triển khai gọi hàm:

• Lặp (Iterative): lặp qua cùng khối mã nhiều lần.
• Đệ quy (Recursive): gọi lại chính hàm đó.

Chương trình Binary Search lặp (Iterative)

#include <stdio.h>

int iterativeBinarySearch(int array[], int start, int end, int element) {
    while (start <= end) {
        int middle = start + (end - start) / 2;
        if (array[middle] == element)
            return middle;
        if (array[middle] < element)
            start = middle + 1;
        else
            end = middle - 1;
    }
    return -1;
}

int main() {
    int array[] = {1, 4, 7, 9, 16, 56, 70};
    int n = 7;
    int element = 16;
    int found = iterativeBinarySearch(array, 0, n - 1, element);

    if (found == -1)
        printf("Khong tim thay phan tu trong mang\n");
    else
        printf("Tim thay phan tu tai chi so: %d\n", found);
    return 0;
}

Kết quả

Tim thay phan tu tai chi so: 4

Chương trình Binary Search đệ quy (Recursive)

#include <stdio.h>

int recursiveBinarySearch(int array[], int start, int end, int element) {
    if (end >= start) {
        int middle = start + (end - start) / 2;
        if (array[middle] == element)
            return middle;
        if (array[middle] > element)
            return recursiveBinarySearch(array, start, middle - 1, element);
        return recursiveBinarySearch(array, middle + 1, end, element);
    }
    return -1;
}

int main() {
    int array[] = {1, 4, 7, 9, 16, 56, 70};
    int n = 7;
    int element = 9;
    int found = recursiveBinarySearch(array, 0, n - 1, element);

    if (found == -1)
        printf("Khong tim thay phan tu trong mang\n");
    else
        printf("Tim thay phan tu tai chi so: %d\n", found);
    return 0;
}

Kết quả

Tim thay phan tu tai chi so: 3