대수 검색으로 알려진 이진 검색은 정렬된 배열에서 요소를 검색하는 검색 알고리즘입니다. 알고리즘은 배열을 재귀적으로 두 개의 반으로 나눕니다. 요소가 중간 위치에 있으면 반환하고 그렇지 않으면 나누기를 호출하고 요소를 찾을 때까지 다시 확인합니다.
작업
알고리즘은 정렬된 배열의 중간 요소를 검색할 요소와 비교하여 작동합니다.
검색 요소가 같음인 경우 중간 요소로 이동한 다음 색인 반환 요소의.
검색 요소가 더 크면 중간 요소보다 왼쪽 하위 배열에서 검색 즉, 중간의 다음 요소에서 배열의 끝까지 하위 배열입니다.
검색 요소가 작은 경우 중간 요소보다 오른쪽 하위 배열에서 검색 즉, 첫 번째 요소에서 배열 중간 이전 요소까지의 하위 배열입니다.
구문
표준 이진 정렬에 대한 호출, 다음 구문이 사용됩니다 -
binary_search(start_address , end_address , element)
매개변수
start_address는 배열의 첫 번째 요소 주소입니다.
end_address는 배열의 마지막 요소의 주소입니다.
element는 배열에서 찾을 요소입니다.
반환
값이 배열의 요소 인덱스와 같은 정수를 반환합니다. 그렇지 않으면 0을 반환합니다.
예시
#include <algorithm>
#include <iostream>
using namespace std;
void printArray(int a[], int arraysize){
for (int i = 0; i < arraysize; ++i)
cout << a[i] << " ";
}
int main(){
int arr[] = {1 , 5, 9, 7 , 3, 2 , 0 , 4};
int sizeofarr = sizeof(arr)/sizeof(arr[0]);
cout<<"The Element of array are :\n";
printArray(arr , sizeofarr);
cout<<"\nSorting Elements of array.";
sort(arr , arr+sizeofarr);
cout<<"\nSorted array is : ";
printArray(arr, sizeofarr);
cout<<"\nElement to be searched is 4";
if(binary_search(arr , arr+sizeofarr , 4))
cout<<"\nElement found ";
else
cout<<"\nElement not found";
} 출력
The Element of array are : 1 5 9 7 3 2 0 4 Sorting Elements of array. Sorted array is : 0 1 2 3 4 5 7 9 Element to be searched is 4