Binary Search (การค้นหาแบบทวิภาค) ในภาษา C

กรณีที่เป็นไปได้ 3 กรณี

1. ค่ากึ่งกลาง = Key → ค้นหาสำเร็จ จบการทำงาน
2. ค่ากึ่งกลาง > Key → ค้นหาต่อในส่วนซ้าย (ค่าน้อยกว่า)
3. ค่ากึ่งกลาง < Key → ค้นหาต่อในส่วนขวา (ค่ามากกว่า)

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

#include <stdio.h>

int main() {
    int a[50], n, i, key, flag = 0;
    int low, mid, high;
    
    printf("Enter number of elements: ");
    scanf("%d", &n);
    
    printf("Enter %d sorted elements: ", n);
    for(i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    printf("Enter key to search: ");
    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 successful - Found at index %d", mid);
    else
        printf("Search unsuccessful - Not found");
    
    return 0;
}

ผลลัพธ์

Enter number of elements: 5
Enter 5 sorted elements: 23 45 57 89 90
Enter key to search: 45
Search successful - Found at index 1

ความซับซ้อนของเวลา (Time Complexity)

• Best Case: O(1) - พบทันทีที่กึ่งกลาง
• Average/Worst Case: O(log n) - ต้องแบ่งครึ่งซ้ำๆ
• Space Complexity: O(1) - ใช้หน่วยความจำคงที่

ข้อจำกัด

• ข้อมูลต้องจัดเรียงล่วงหน้า
• เข้าถึงข้อมูลได้แบบสุ่ม (Random Access) เช่น Array