การค้นหาแบบไบนารีเป็นอัลกอริธึมการค้นหาที่ค้นหาตำแหน่งของค่าเป้าหมายภายในอาร์เรย์ที่จัดเรียง การค้นหาแบบไบนารีจะเปรียบเทียบค่าเป้าหมายกับองค์ประกอบตรงกลางของอาร์เรย์ที่จัดเรียง ความซับซ้อนของเวลาของการค้นหาไบนารีคือ O(1) นี่คือโปรแกรม C++ ที่เรานำไปใช้งานต่างๆ ฟังก์ชันการค้นหาไบนารีใน C++ STL
อัลกอริทึม
Begin Initialize the vector of integer values. The functions are used here: binary_search(start_pointer, end_pointer, value) = Returns true if the value present in array otherwise false. lower_bound(start_pointer, end_pointer, value) = Returns pointer to “position of value” if container contains 1 occurrence of value. Returns pointer to “first position of value” if container contains multiple occurrence of value. Returns pointer to “position of next higher number than value” if container does not contain occurrence of value. upper_bound(start_pointer, end_pointer, value) = Returns pointer to “position of next higher valuethan value” if container contains 1 occurrence of value. Returns pointer to “first position of next higher number than last occurrence of value” if container contains multiple occurrence of value. Returns pointer to “position of next higher number than value” if container does not contain occurrence of value. Print the results. End.
โค้ดตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {6,7,10,14,16,20};
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;
cout << "The position of 7 using lower_bound ";
cout << lower_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
cout << "The position of 7 using upper_bound ";
cout << upper_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
} ผลลัพธ์
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
