Tìm phần tử nhỏ nhất mảng bằng tìm kiếm nhị phân trong C

C cung cấp hai kỹ thuật tìm kiếm: tuyến tính và nhị phân.

Tìm kiếm nhị phân

• Chỉ áp dụng cho danh sách đã sắp xếp.
• Chia danh sách thành hai phần bằng nhau.
• So sánh khóa với phần tử giữa.

Ba tình huống:

• Phần tử giữa khớp khóa -> tìm thấy thành công.
• Phần tử giữa > khóa -> tìm tiếp partition trái.
• Phần tử giữa < khóa -> tìm tiếp partition phải.

Đầu vào - Danh sách không sắp xếp, khóa.

Đầu ra - Thành công nếu tìm thấy, thất bại nếu không.

key = 20 mid = (low + high) / 2

Chương trình 1

Chương trình C tìm phần tử nhỏ nhất bằng tìm kiếm nhị phân:

#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: "); 
    for(i = 0; i < n; i++) 
        scanf("%d", &a[i]); 
    printf("Nhap phan tu 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 kiem thanh cong"); 
    else 
        printf("Tim kiem that bai"); 
    return 0; 
}

Đầu ra

Kết quả chạy chương trình:

Lan 1: Nhap so phan tu: 5 
Phan tu: 12 34 11 56 67 
Tim: 45 
That bai 
Lan 2: Nhap so phan tu: 3 
Phan tu: 12 34 56 
Tim: 34 
Thanh cong

Chương trình 2

Chương trình C khác tìm phần tử nhỏ nhất bằng tìm kiếm nhị phân:

#include <stdio.h> 
void Bmin(int *a, int i, int n){ 
    int j, temp; 
    temp = a[i]; 
    j = 2 * i; 
    while (j <= n){ 
        if (j < n && a[j+1] > a[j]) 
            j = j + 1; 
        if (temp < a[j]) 
            break; 
        else if (temp >= a[j]){ 
            a[j / 2] = a[j]; 
            j = 2 * j; 
        } 
    } 
    a[j/2] = temp; 
    return; 
} 
int binarysearchmin(int *a, int n){ 
    int i; 
    for(i = n/2; i >= 1; i--){ 
        Bmin(a, i, n); 
    } 
    return a[1]; 
} 
int main(){ 
    int n, i, x, min; 
    int a[20]; 
    printf("Nhap so phan tu mang\n"); 
    scanf("%d", &n); 
    printf("\nNhap %d phan tu: ", n); 
    for (i = 1; i <= n; i++){ 
        scanf("%d", &a[i]); 
    } 
    min = binarysearchmin(a, n); 
    printf("\nPhan tu nho nhat mang: %d", min); 
    return 0; 
}

Đầu ra

Kết quả chạy chương trình:

Nhap so phan tu mang: 5 
Nhap 5 phan tu: 12 23 34 45 56 
Phan tu nho nhat mang: 12