ฟังก์ชันการค้นหาแบบทวิภาคใน C++ STL (binary_search, lower_bound, upper_bound)

การค้นหาแบบทวิภาค (Binary Search) เป็นอัลกอริทึมที่ค้นหาองค์ประกอบโดยเปรียบเทียบกับค่ากลางของอาร์เรย์และแบ่งออกตามค่านั้น ทำซ้ำจนกว่าจะพบองค์ประกอบ อาร์เรย์ต้องถูกจัดเรียงล่วงหน้าก่อนใช้งาน ความซับซ้อนด้านเวลาคือ O(log n) ทำให้เป็นสิ่งสำคัญที่โปรแกรมเมอร์ควรรู้จักฟังก์ชันสำเร็จรูปใน STL เพื่อลดเวลาเขียนโค้ด

ฟังก์ชันที่เกี่ยวข้องกับการค้นหาแบบทวิภาคใน STL ได้แก่ lower_bound, upper_bound, และ binary_search

lower_bound

คืนตำแหน่งที่องค์ประกอบถูกพบ (หรือตำแหน่งที่ควรจะอยู่)

รูปแบบการใช้งาน

lower_bound(start_pointer, end_pointer, element)

พารามิเตอร์

• start_pointer - ตัวชี้จุดเริ่มต้นของโครงสร้างข้อมูล
• end_pointer - ตัวชี้จุดสิ้นสุดของโครงสร้างข้อมูล
• element - องค์ประกอบที่ต้องการค้นหา

ค่าที่คืน

• ถ้าองค์ปรากฏ 1 ครั้ง - คืนตำแหน่งขององค์ประกอบนั้น
• ถ้าองค์ปรากฏหลายครั้ง - คืนตำแหน่งขององค์ประกอบแรกที่พบ
• ถ้าไม่พบองค์ประกอบ - คืนตำแหน่งของตัวเลขที่มากกว่าองค์ประกอบที่ค้นหา (ตำแหน่งที่ควรแทรกเข้าไป)

ดัชนี (index) สามารถหาได้จากการลบตำแหน่งฐาน (base position) ของโครงสร้าง

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> sortedarray = {2, 5, 7, 8, 15, 20};
    vector<int> sortedarray2 = {2, 3, 4, 6, 9, 23};
    vector<int> sortedarray3 = {2, 5, 7, 7, 15, 20};

    cout << "The position of element 7 found using lower_bound function :";
    cout << "\nCase 1 : When element is present in array but only once ";
    cout << lower_bound(sortedarray.begin(), sortedarray.end(), 7) - sortedarray.begin();
    cout << "\nCase 2 : When element is present more than one times in the array ";
    cout << lower_bound(sortedarray3.begin(), sortedarray3.end(), 7) - sortedarray3.begin();
    cout << "\nCase 3 : When element is not present in the array ";
    cout << lower_bound(sortedarray2.begin(), sortedarray2.end(), 7) - sortedarray2.begin();
}

ผลลัพธ์

The position of element 7 found using lower_bound function :
Case 1 : When element is present in array but only once 2
Case 2 : When element is present more than one times in the array 2
Case 3 : When element is not present in the array 4

upper_bound

คืนตำแหน่งขององค์ประกอบที่มีค่ามากกว่าองค์ประกอบที่ระบุ

รูปแบบการใช้งาน

upper_bound(start_pointer, end_pointer, element)

ค่าที่คืน

• ถ้าองค์ปรากฏ 1 ครั้ง - คืนตำแหน่งขององค์ประกอบถัดไป (ค่ามากกว่า)
• ถ้าองค์ปรากฏหลายครั้ง - คืนตำแหน่งถัดจากองค์ประกอบสุดท้ายที่ตรงกัน
• ถ้าไม่พบองค์ประกอบ - คืนตำแหน่งของตัวเลขที่มากกว่าองค์ประกอบที่ค้นหา

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> sortedarray = {2, 5, 7, 8, 15, 20};
    vector<int> sortedarray2 = {2, 3, 4, 6, 9, 23};
    vector<int> sortedarray3 = {2, 5, 7, 7, 15, 20};

    cout << "The position of element 7 found using upper_bound function :";
    cout << "\nCase 1 : When element is present in array but only once ";
    cout << upper_bound(sortedarray.begin(), sortedarray.end(), 7) - sortedarray.begin();
    cout << "\nCase 2 : When element is present more than one times in the array ";
    cout << upper_bound(sortedarray3.begin(), sortedarray3.end(), 7) - sortedarray3.begin();
    cout << "\nCase 3 : When element is not present in the array ";
    cout << upper_bound(sortedarray2.begin(), sortedarray2.end(), 7) - sortedarray2.begin();
}

ผลลัพธ์

The position of element 7 found using upper_bound function :
Case 1 : When element is present in array but only once 3
Case 2 : When element is present more than one times in the array 4
Case 3 : When element is not present in the array 4

binary_search

ตรวจสอบว่าองค์ประกอบมีอยู่ในโครงสร้างข้อมูลหรือไม่

รูปแบบการใช้งาน

binary_search(start_pointer, end_pointer, element)

ค่าที่คืน

คืน true หากพบองค์ประกอบ มิฉะนั้นคืน false

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> sortedarray = {6, 15, 21, 27, 39, 42};
    cout << "The element to be found in the array is 21\n";
    if (binary_search(sortedarray.begin(), sortedarray.end(), 21))
        cout << "The element is found";
    else
        cout << "The element is not found";

    cout << "\nThe element to be found in the array is 5\n";
    if (binary_search(sortedarray.begin(), sortedarray.end(), 5))
        cout << "The element is found";
    else
        cout << "The element is not found";
}

ผลลัพธ์

The element to be found in the array is 21
The element is found
The element to be found in the array is 5
The element is not found