Binary Search는 배열을 반으로 하고 반으로 검색을 반복하여 정렬된 배열에서 필요한 요소를 찾는 방법입니다.
이 방법은 전체 배열로 시작하여 수행됩니다. 그런 다음 절반입니다. 필요한 데이터 값이 배열의 중간에 있는 요소보다 크면 배열의 위쪽 절반이 고려됩니다. 그렇지 않으면 아래쪽 절반이 고려됩니다. 이것은 필요한 데이터 값을 얻거나 나머지 배열이 비어 있을 때까지 계속 수행됩니다.
다음은 C++에서 바이너리 검색을 보여주는 프로그램입니다.
예시
#include
using namespace std;
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
}
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num;
cout << "Enter the number to search: \n";
cin >> num;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1){
cout<< num <<" is not present in the array";
}else{
cout<< num <<" is present at index "<< index <<" in the array";
}
return 0;
} 출력
Enter the numberto search 20 20 is present at index 5 in the array
위 프로그램에서 binarySearch()는 이진 검색을 사용하여 배열에서 필요한 요소를 찾는 데 사용되는 재귀 함수입니다. 이 함수는 배열, 하한 및 상한, 찾을 수를 매개변수로 사용합니다. 이것은 아래에 나와 있습니다.
int binarySearch(int arr[], int p, int r, int num)
그런 다음 배열의 중간점이 계산됩니다. 중간점의 값이 num과 같으면 반환됩니다. 값이 num보다 크면 배열은 하한 p와 상한 mid-1을 사용하여 자신을 재귀적으로 호출합니다. 값이 num보다 작으면 배열은 하한 mid+1 및 상한 r을 사용하여 자신을 재귀적으로 호출합니다. 이는 다음 코드 스니펫에서 확인할 수 있습니다.
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
} main() 함수에서 배열 arr[]이 정의됩니다. 배열의 크기가 계산되고 찾을 숫자가 지정됩니다. 그런 다음 숫자의 인덱스를 찾기 위해 binarySearch()가 호출됩니다. binarySearch()에 의해 반환된 값이 -1이면 숫자가 배열에 없는 것입니다. 그렇지 않으면 인덱스 값이 반환됩니다. 이것은 아래와 같습니다.
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num = 33;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1)
cout<< num <<" is not present in the array";
else
cout<< num <<" is present at index "<< index <<" in the array";
return 0;
}