이진 검색은 배열의 중간 값과 비교하고 값으로 나누어 요소를 검색하는 검색 알고리즘입니다. 알고리즘은 요소를 찾을 때까지 이 작업을 반복적으로 수행합니다.
이진 검색을 적용하려면 배열을 정렬해야 합니다.
이진 검색의 시간 복잡도는 대수 입니다. 주문하다. 이것이 프로그래머가 알고리즘 코딩 시간을 줄이기 위해 구현과 함께 바이너리 검색과 관련된 약어를 아는 것이 매우 중요한 이유입니다. 여기에서는 표준 템플릿 라이브러리(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 검색 구조의 끝점 메모리 위치를 보유하는 포인터입니다.
요소 함수를 사용하여 찾을 요소입니다.
요소가 구조에 있으면 함수는 true를 반환합니다. 그렇지 않으면 false를 반환합니다.
예시
#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