Binary Search — Tìm kiếm nhị phân

#include <stdio.h>

/**
 * Binary Search trên mảng đã sắp xếp tăng dần
 * Trả về chỉ số của target, hoặc -1 nếu không tìm thấy
 */
int binarySearch(int a[], int n, int target) {
    int lo = 0, hi = n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // Tránh tràn số (overflow)

        if (a[mid] == target)
            return mid;           // Tìm thấy!
        else if (a[mid] < target)
            lo = mid + 1;          // Tìm nửa phải
        else
            hi = mid - 1;          // Tìm nửa trái
    }

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

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

    int idx = binarySearch(a, n, target);

    if (idx != -1)
        printf("Tìm thấy %d tại chỉ số %d\n", target, idx);
    else
        printf("Không tìm thấy %d\n", target);

    return 0;
}