Tìm kiếm nhị phân (Binary Search) trong C

Tìm kiếm nhị phân chỉ áp dụng cho danh sách đã sắp xếp. Chia danh sách làm hai nửa, so sánh khóa (key) với phần tử giữa.

• Nếu phần tử giữa = key → tìm thấy.
• Nếu phần tử giữa > key → tìm nửa trái.
• Nếu phần tử giữa < key → tìm nửa phải.

Đầu vào/Đầu ra

• Input: danh sách đã sắp xếp, key cần tìm.
• Output: "Thành công" nếu tìm thấy, "Thất bại" nếu không.

Chương trình

#include <stdio.h>
int main() {
    int a[50], n, i, key, flag = 0, low, mid, high;
    printf("Nhap so phan tu: ");
    scanf("%d", &n);
    printf("Nhap cac phan tu (da sap xep): ");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("Nhap gia tri can tim: ");
    scanf("%d", &key);
    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] == key) {
            flag = 1;
            break;
        } else if (a[mid] > key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    if (flag == 1)
        printf("Tim thay!\n");
    else
        printf("Khong tim thay!\n");
    return 0;
}

Kết quả

Nhap so phan tu: 5
Nhap cac phan tu: 23 45 57 89 90
Nhap gia tri can tim: 45
Tim thay!