ฟังก์ชัน Binary Search ใน C++ STL (binary_search, lower_bound และ upper_bound)

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

ควรจัดเรียงอาร์เรย์เพื่อใช้การค้นหาแบบไบนารีกับอาร์เรย์

ความซับซ้อนของเวลาของการค้นหาไบนารีเป็นของ ลอการิทึม คำสั่ง. นั่นเป็นเหตุผลว่าทำไมจึงเป็นสิ่งสำคัญมากสำหรับโปรแกรมเมอร์ที่จะรู้ว่าชวเลขที่เกี่ยวข้องกับการค้นหาแบบไบนารีพร้อมกับการใช้งานเพื่อลดเวลาในการเขียนโค้ดอัลกอริธึม ฟังก์ชันที่เกี่ยวข้องกับอัลกอริธึมการค้นหาแบบไบนารีที่รวมอยู่ในไลบรารีเทมเพลตมาตรฐาน (STL) มีการกล่าวถึงที่นี่

ขอบล่าง − การค้นหาขอบเขตล่างจะส่งคืนตำแหน่งที่พบองค์ประกอบ

ไวยากรณ์

lower_bound(start_pointer , end_pointer, element )

ที่นี่

start_pointer เป็นตัวชี้ที่เก็บตำแหน่งหน่วยความจำของจุดเริ่มต้นของโครงสร้างการค้นหา

end_pointer เป็นตัวชี้ที่เก็บตำแหน่งหน่วยความจำของจุดสิ้นสุดของโครงสร้างการค้นหา

องค์ประกอบ เป็นองค์ประกอบที่จะพบได้โดยใช้ฟังก์ชัน

ฟังก์ชันจะคืนค่าดัชนีขององค์ประกอบที่จะพบ

ค่าที่ส่งกลับอาจใช้ค่าได้หลายค่า -

หากองค์ประกอบเกิดขึ้นครั้งเดียวในโครงสร้าง ตำแหน่งจะถูกส่งคืน

หากองค์ประกอบเกิดขึ้นมากกว่าหนึ่งครั้งในโครงสร้าง ตำแหน่งขององค์ประกอบแรกจะถูกส่งคืน

หากองค์ประกอบไม่เกิดขึ้นในโครงสร้าง ระบบจะส่งคืนตำแหน่งของหมายเลขที่สูงกว่าถัดไปจากองค์ประกอบ

ดัชนี ขององค์ประกอบใดๆ หาได้โดยการลบตำแหน่งฐานของโครงสร้าง

ตัวอย่าง

#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(start_pointer , end_pointer, element)

ที่นี่

start_pointer เป็นตัวชี้ที่เก็บตำแหน่งหน่วยความจำของจุดเริ่มต้นของโครงสร้างการค้นหา

end_pointer เป็นตัวชี้ที่เก็บตำแหน่งหน่วยความจำของจุดสิ้นสุดของโครงสร้างการค้นหา

องค์ประกอบ เป็นองค์ประกอบที่จะพบได้โดยใช้ฟังก์ชัน

ฟังก์ชันส่งคืนดัชนีขององค์ประกอบที่มีค่ามากกว่ามูลค่าขององค์ประกอบ

ค่าที่ส่งกลับอาจใช้ค่าได้หลายค่า -

หากองค์ประกอบเกิดขึ้นครั้งเดียวในโครงสร้าง ตำแหน่งถัดไปขององค์ประกอบที่สูงกว่าจะถูกส่งคืน

หากองค์ประกอบเกิดขึ้นมากกว่าหนึ่งครั้งในโครงสร้าง ตำแหน่งขององค์ประกอบถัดไปขององค์ประกอบสุดท้ายจะถูกส่งคืน

หากองค์ประกอบไม่เกิดขึ้นในโครงสร้าง ตำแหน่งของหมายเลขถัดไปที่สูงกว่าองค์ประกอบจะถูกส่งคืน

ดัชนี ขององค์ประกอบใดๆ หาได้โดยการลบตำแหน่งฐานของโครงสร้าง

ตัวอย่าง

#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)

ที่นี่

start_pointer เป็นตัวชี้ที่เก็บตำแหน่งหน่วยความจำของจุดเริ่มต้นของโครงสร้างการค้นหา

end_pointer เป็นตัวชี้ที่เก็บตำแหน่งหน่วยความจำของจุดสิ้นสุดของโครงสร้างการค้นหา

องค์ประกอบ เป็นองค์ประกอบที่จะพบได้โดยใช้ฟังก์ชัน

หากมีองค์ประกอบอยู่ในโครงสร้าง ฟังก์ชันจะคืนค่าเป็น จริง ไม่เช่นนั้นจะคืนค่าเท็จ

ตัวอย่าง

#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