이진 검색 알고리즘은 비교 및 분할 메커니즘을 기반으로 하는 알고리즘입니다. 이진 검색 알고리즘은 반간 검색, 대수 검색 또는 이진 절단이라고도 합니다. . 이진 검색 알고리즘은 정렬된 배열에서 대상 값의 위치를 검색합니다. 대상 값을 배열의 중간 요소와 비교합니다. 요소가 대상 요소와 같으면 알고리즘이 색인을 반환합니다. 발견된 요소의 그리고 그들이 같지 않으면 검색 알고리즘은 해당 배열의 절반 섹션을 사용합니다. 값의 비교를 기반으로 알고리즘은 전반부(값이 중간보다 작을 때)와 후반부( 값이 중간보다 큰 경우). 다음 어레이 절반에도 동일하게 수행합니다.
Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8 설명
우리 어레이의 경우 -
55를 55보다 작은 18인 배열의 중간 요소와 비교할 것이므로 배열의 후반부, 즉 배열 {24, 45, 55, 99}를 사용합니다. 다시 중간은 55입니다. 검색 요소의 값을 확인하십시오. 값이 일치하면 이 값의 인덱스를 8로 반환합니다.
검색 요소가 중간보다 작으면 전반부를 사용하고 배열의 중간에서 요소를 찾을 때까지 계속합니다.
이진 검색을 구현하려면 두 가지 방법으로 코드를 작성할 수 있습니다. 이 두 가지 방법은 이진 검색 요소를 확인하는 함수를 호출하는 방식으로만 지연됩니다. 그들은:
-
반복 사용 - 이것은 중간 요소의 동등성을 검사하는 함수 내부의 루프를 사용하는 것을 의미합니다.
-
사용 이 메서드에서 함수는 다른 값 집합으로 자신을 계속해서 호출합니다.
예시
#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
int A[] = {0,12,6,12,12,18,34,45,55,99};
int n=55;
printf("%d is found at Index %d \n",n,iterativeBsearch(A,10,n));
return 0;
}
int iterativeBsearch(int A[], int size, int element) {
int start = 0;
int end = size-1;
while(start<=end) {
int mid = (start+end)/2;
if( A[mid] == element) {
return mid;
} else if( element < A[mid] ) {
end = mid-1;
} else {
start = mid+1;
}
}
return -1;
} 출력
55 is found at Index 8
예시
#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
if(start>end) return -1;
int mid = (start+end)/2;
if( A[mid] == element ) return mid;
else if( element < A[mid] )
RecursiveBsearch(A, start, mid-1, element);
else
RecursiveBsearch(A, mid+1, end, element);
}
int main() {
int A[] = {0,2,6,11,12,18,34,45,55,99};
int n=55;
printf("%d is found at Index %d \n",n,RecursiveBsearch(A,0,9,n));
return 0;
} 출력
55 is found at Index 8