Các hàm tìm kiếm nhị phân trong C ++ STL

Tìm kiếm nhị phân là một thuật toán tìm kiếm để tìm vị trí của giá trị đích trong một mảng được sắp xếp. Tìm kiếm nhị phân so sánh giá trị đích với phần tử giữa của mảng đã sắp xếp. Độ phức tạp về thời gian của tìm kiếm nhị phân là O (1). Đây là một chương trình C ++ mà chúng tôi thực hiện nhiều chương trình khác nhau. Các hàm tìm kiếm nhị phân trong C ++ STL

Thuật toán

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.

Mã mẫu

#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;
}

Đầu ra

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