อัลกอริทึม การค้นหาแบบไบนารี (Binary Search) ใน C++- คำอธิบาย ตัวอย่าง และโค้ด

อัลกอริทึมการค้นหาแบบไบนารีเป็นวิธีที่มีประสิทธิภาพมากกว่าในการค้นหาองค์ประกอบเฉพาะในรายการที่เรียงลำดับ ซึ่งแตกต่างจากการค้นหาเชิงเส้นซึ่งจะตรวจสอบองค์ประกอบตามลำดับ การค้นหาแบบไบนารีจะแบ่งรายการออกเป็นครึ่งๆ และเปรียบเทียบองค์ประกอบเป้าหมายกับองค์ประกอบตรงกลาง กระบวนการนี้ทำซ้ำจนกว่าจะพบองค์ประกอบเป้าหมายหรือช่วงการค้นหาว่างเปล่า

มันทำงานอย่างไร

1. เริ่มต้นด้วยรายการที่เรียงลำดับทั้งหมด
2. ค้นหาองค์ประกอบตรงกลางของช่วงการค้นหาปัจจุบัน
3. เปรียบเทียบองค์ประกอบตรงกลางกับค่าเป้าหมาย
4. หากองค์ประกอบตรงกลางเท่ากับค่าเป้าหมาย การค้นหาจะสำเร็จ
5. หากองค์ประกอบตรงกลางมากกว่าเป้าหมาย ให้ค้นหาในครึ่งซ้ายของช่วง
6. หากองค์ประกอบตรงกลางมีขนาดเล็กกว่าเป้าหมาย ให้ค้นหาในครึ่งขวาของช่วง
7. ทำซ้ำขั้นตอนที่ 2-6 จนกว่าจะพบองค์ประกอบเป้าหมายหรือช่วงการค้นหาว่างเปล่า

ตัวอย่าง

ลองพิจารณารายการของจำนวนเต็มและต้องการหาหมายเลข 34 โดยใช้การค้นหาแบบไบนารี

รายการเรียง: {12, 23, 34, 45, 56, 67, 89, 90}

1. เริ่มต้นด้วยรายการทั้งหมด
2. องค์ประกอบกลาง: 56(ตำแหน่ง 4) เปรียบเทียบกับ 34
3. 56 มากกว่า 34 ค้นหาในครึ่งซ้าย
4. องค์ประกอบตรงกลางใหม่: 23(ตำแหน่ง 1) เปรียบเทียบกับ 34
5. 23 น้อยกว่า 34 ค้นหาในครึ่งขวา
6. องค์ประกอบตรงกลางใหม่: 45(ตำแหน่ง 3) เปรียบเทียบกับ 34
7. 45 มากกว่า 34 ค้นหาในครึ่งซ้าย
8. องค์ประกอบตรงกลางใหม่: 34(ตำแหน่ง 2) พบเป้าหมายแล้ว

ตัวอย่างโค้ดในภาษา C++

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

ในตัวอย่างที่กำหนด binarySearch ฟังก์ชันนี้ใช้เพื่อค้นหาหมายเลข 34 ในรายการจำนวนเต็มที่เรียงลำดับ ผลลัพธ์จะเป็นตำแหน่ง 34 ในรายการ(ตำแหน่งเริ่มต้นจาก 0) หรือ -1 หากไม่พบหมายเลข