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

Binary Search คืออะไร?

Binary Search (การค้นหาแบบทวิภาค) เป็นอัลกอริทึมค้นหาที่มีประสิทธิภาพ ใช้กับข้อมูลที่ จัดเรียงแล้ว ทำงานโดยแบ่งช่วงค้นหาลงครึ่งเรื่อยๆ จนพบค่าที่ต้องการหรือช่วงค้นหาว่างเปล่า

หลักการทำงาน

1. กำหนดช่วงค้นหา: Low = 0, High = n-1
2. คำนวณตำแหน่งกลาง: mid = (Low + High) / 2
3. เปรียบเทียบค่าที่ mid กับค่าที่ต้องการค้นหา (key):
   • ถ้า arr[mid] == key → พบแล้ว คืนค่า mid
   • ถ้า arr[mid] < key → ค้นหาต่อด้านขวา (Low = mid + 1)
   • ถ้า arr[mid] > key → ค้นหาต่อด้านซ้าย (High = mid - 1)
4. ทำซ้ำจนกว่า Low > High (ไม่พบ) หรือพบค่าที่ต้องการ

ตัวอย่างการค้นหา

อาร์เรย์: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ค้นหา 8

• รอบ 1: Low=0, High=9, mid=4, arr[4]=5 < 8 → Low=5
• รอบ 2: Low=5, High=9, mid=7, arr[7]=8 == 8 → พบที่ index 7

ใช้เพียง 2 รอบ เทียบกับ Linear Search ใช้ 8 รอบ

ความซับซ้อน

• เวลา: O(log n)
• พื้นที่: O(1) แบบ Iterative, O(log n) แบบ Recursive

ตัวอย่างโค้ด C++ (Iterative)

int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2; // ป้องกัน overflow
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1; // ไม่พบ
}

ตัวอย่างโค้ด C++ (Recursive)

int binarySearchRecursive(int arr[], int low, int high, int key) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == key) return mid;
    if (arr[mid] < key)
        return binarySearchRecursive(arr, mid + 1, high, key);
    return binarySearchRecursive(arr, low, mid - 1, key);
}