Tìm kiếm nhị phân là một thuật toán tìm kiếm tìm kiếm một phần tử bằng cách so sánh nó với giá trị giữa của mảng và chia nó dựa trên giá trị. Thuật toán thực hiện điều này lặp đi lặp lại cho đến khi phần tử được tìm thấy.
Mảng phải được sắp xếp để áp dụng tìm kiếm nhị phân cho nó.
Độ phức tạp về thời gian của tìm kiếm nhị phân là logarit gọi món. Đó là lý do tại sao điều rất quan trọng đối với các lập trình viên là phải biết các phím tắt cũng liên quan đến tìm kiếm nhị phân cùng với các triển khai của nó để giảm thời gian viết mã thuật toán. Các chức năng liên quan đến thuật toán tìm kiếm nhị phân có trong thư viện mẫu chuẩn (STL) được thảo luận tại đây.
low_bound - Tìm kiếm giới hạn dưới trả về vị trí nơi phần tử được tìm thấy.
Cú pháp
lower_bound(start_pointer , end_pointer, element )
Đây,
start_pointer là con trỏ giữ vị trí bộ nhớ của điểm bắt đầu của cấu trúc tìm kiếm.
end_pointer là một con trỏ giữ vị trí bộ nhớ của điểm cuối của cấu trúc tìm kiếm.
phần tử là phần tử được tìm thấy bằng cách sử dụng hàm.
Hàm trả về chỉ mục của phần tử sẽ được tìm thấy.
Giá trị trả về có thể nhận nhiều giá trị -
Nếu phần tử xuất hiện một lần trong cấu trúc, vị trí sẽ được trả về.
Nếu phần tử xuất hiện nhiều lần trong cấu trúc, thì vị trí của phần tử đầu tiên sẽ được trả về.
Nếu phần tử không xuất hiện trong cấu trúc, thì vị trí của số tiếp theo cao hơn phần tử sẽ được trả về.
Chỉ mục của bất kỳ phần tử nào được tìm thấy bằng cách trừ đi vị trí cơ bản của cấu trúc.
Ví dụ
#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();
} Đầu ra
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 - Tìm kiếm giới hạn trên trả về vị trí của phần tử cao hơn phần tử được truyền vào.
Cú pháp
upper_bound(start_pointer , end_pointer, element)
Đây,
start_pointer là con trỏ giữ vị trí bộ nhớ của điểm bắt đầu của cấu trúc tìm kiếm.
end_pointer là một con trỏ giữ vị trí bộ nhớ của điểm cuối của cấu trúc tìm kiếm.
phần tử là phần tử được tìm thấy bằng cách sử dụng hàm.
Hàm trả về chỉ số của phần tử có giá trị lớn hơn giá trị của phần tử.
Giá trị trả về có thể nhận nhiều giá trị -
Nếu phần tử xuất hiện một lần trong cấu trúc, thì vị trí phần tử cao hơn tiếp theo sẽ được trả về.
Nếu phần tử xuất hiện nhiều lần trong cấu trúc, thì vị trí của phần tử tiếp theo của phần tử cuối cùng sẽ được trả về.
Nếu phần tử không xuất hiện trong cấu trúc, thì vị trí của số cao hơn phần tử tiếp theo sẽ được trả về.
Chỉ mục của bất kỳ phần tử nào được tìm thấy bằng cách trừ đi vị trí cơ bản của cấu trúc.
Ví dụ
#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();
} Đầu ra
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 là một hàm kiểm tra xem phần tử có trong cấu trúc hay không.
Cú pháp
binary_search(start_pointer , end_pointer, element)
Đây,
start_pointer là con trỏ giữ vị trí bộ nhớ của điểm bắt đầu của cấu trúc tìm kiếm.
end_pointer là một con trỏ giữ vị trí bộ nhớ của điểm cuối của cấu trúc tìm kiếm.
phần tử là phần tử được tìm thấy bằng cách sử dụng hàm.
Nếu Phần tử có trong cấu trúc, hàm trả về true. Nếu không, nó sẽ trả về false.
Ví dụ
#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";
} Đầu ra
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