หาค่าต่ำสุดในอาร์เรย์ด้วย Binary Search ในภาษา C

การใช้ Binary Search หาค่าต่ำสุด (Minimum) ในอาร์เรย์

ข้อสังเกต: Binary Search ต้องการข้อมูลที่เรียงลำดับแล้ว บทความนี้แสดง 2 วิธี: 1) ค้นหาค่าที่กำหนด (Key) 2) หาค่าต่ำสุดโดยใช้ Heap property (Binary Heap)

โปรแกรม 1: Binary Search ธรรมดา (ค้นหา Key)

#include <stdio.h>

int main() {
    int a[50], n, i, key, flag = 0, low, mid, high;
    printf("enter the no: of elements: ");
    scanf("%d", &n);
    printf("enter the elements: ");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("enter a key element: ");
    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("search is successful");
    else
        printf("search is unsuccessful");
    return 0;
}

โปรแกรม 2: หาค่าต่ำสุดด้วย Binary Heap (Min-Heap)

#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("Enter no of elements in an array\n");
    scanf("%d", &n);
    printf("\nEnter %d elements: ", n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    min = binarysearchmin(a, n);
    printf("\nminimum element in an array is : %d", min);
    return 0;
}

ตัวอย่าง Output โปรแกรม 2

Enter no of elements in an array 5
Enter 5 elements: 12 23 34 45 56
minimum element in an array is: 12

หมายเหตุ: โปรแกรม 2 ใช้หลัก Min-Heap โดยดัชนีเริ่มที่ 1 (a[1] คือ root) ฟังก์ชัน Bmin ปรับโครงสร้างให้เป็น Heap แล้วค่าต่ำสุดอยู่ a[1]