Binary Search (การค้นหาแบบทวิภาค) เป็นอัลกอริธึมค้นหาที่หาตำแหน่งของค่าเป้าหมายภายในอาร์เรย์ที่เรียงลำดับแล้ว โดยเปรียบเทียบค่าเป้าหมายกับองค์ประกอบกลาง ความซับซ้อนของเวลาคือ O(log n) (ไม่ใช่ O(1) ตามที่ระบุในต้นฉบับ)
อัลกอริธึมและฟังก์ชันที่ใช้
- binary_search(first, last, value) – คืน true หากพบ value ในช่วง มิฉะนั้นคืน false
- lower_bound(first, last, value) – คืน iterator ไปยังตำแหน่งแรกที่ไม่ น้อยกว่า value (first position ≥ value)
- ถ้ามี value อยู่ 1 ตัว → ตำแหน่งของ value
- ถ้ามี value ซ้ำหลายตัว → ตำแหน่งแรกของ value
- ถ้าไม่มี value → ตำแหน่งของค่าที่มากกว่า value ถัดไป
- upper_bound(first, last, value) – คืน iterator ไปยังตำแหน่งแรกที่ มากกว่า value (first position > value)
- ถ้ามี value อยู่ 1 ตัว → ตำแหน่งถัดจาก value
- ถ้ามี value ซ้ำหลายตัว → ตำแหน่งถัดจากตัวสุดท้ายของ value
- ถ้าไม่มี value → ตำแหน่งของค่าที่มากกว่า value ถัดไป (เท่ากับ lower_bound)
โค้ดตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {6, 7, 10, 14, 16, 20};
// binary_search
if (binary_search(a.begin(), a.end(), 50))
cout << "50 exists in vector";
else
cout << "50 does not exist";
cout << endl;
if (binary_search(a.begin(), a.end(), 7))
cout << "7 exists in the vector";
else
cout << "7 does not exist";
cout << endl;
// lower_bound: ตำแหน่งแรกที่ >= 7
cout << "The position of 7 using lower_bound: ";
cout << (lower_bound(a.begin(), a.end(), 7) - a.begin());
cout << endl;
// upper_bound: ตำแหน่งแรกที่ > 7
cout << "The position of 7 using upper_bound: ";
cout << (upper_bound(a.begin(), a.end(), 7) - a.begin());
cout << endl;
// ตัวอย่างกับค่าที่ไม่มีใน vector
cout << "lower_bound of 8: " << (lower_bound(a.begin(), a.end(), 8) - a.begin()) << endl;
cout << "upper_bound of 8: " << (upper_bound(a.begin(), a.end(), 8) - a.begin()) << endl;
return 0;
}
ผลลัพธ์
50 does not exist 7 exists in the vector The position of 7 using lower_bound: 1 The position of 7 using upper_bound: 2 lower_bound of 8: 2 upper_bound of 8: 2
สรุป: lower_bound และ upper_bound มีประโยชน์มากสำหรับการหาช่วงของค่าที่ซ้ำกัน (equal_range = pair(lower_bound, upper_bound)) และการแทรกค่าใหม่โดยรักษาลำดับ
