반간 검색, 대수 검색 또는 이진 절단이라고도 하는 이진 검색은 정렬된 배열 내에서 대상 값의 위치를 찾는 검색 알고리즘입니다. 이진 검색은 대상 값을 배열의 중간 요소와 비교합니다. 동일하지 않은 경우 목표가 놓일 수 없는 절반이 제거되고 나머지 절반에 대해 검색이 계속되며, 다시 중간 요소를 사용하여 목표 값과 비교하고 목표 값을 찾을 때까지 이를 반복합니다. 나머지 절반이 비어 있는 상태에서 검색이 끝나면 대상이 어레이에 없습니다. 아이디어는 간단하지만 이진 검색을 올바르게 구현하려면 종료 조건 및 중간점 계산에 대한 몇 가지 미묘함에 주의해야 합니다. 특히 배열의 값이 범위의 모든 정수가 아닌 경우에는 더욱 그렇습니다.
이진 검색은 가장 널리 사용되는 검색 알고리즘입니다. 효율적이며 문제를 해결하는 데 사용되는 가장 일반적으로 사용되는 기술 중 하나입니다.
세계의 모든 이름을 순서대로 나열하고 특정 이름의 위치를 검색하려는 경우 이진 검색은 최대 35회 반복하여 수행합니다.
이진 검색은 정렬된 요소 집합에서만 작동합니다. 컬렉션에서 이진 검색을 사용하려면 먼저 컬렉션을 정렬해야 합니다.
이진 검색을 사용하여 정렬된 집합에 대한 작업을 수행하는 경우 검색되는 값을 기준으로 항상 반복 횟수를 줄일 수 있습니다.
다음 배열을 고려해보자 -
선형 검색을 사용하여 요소 8의 위치는 9번째 반복에서 결정됩니다.
이진 검색을 사용하여 반복 횟수를 줄이는 방법을 살펴보겠습니다. 검색을 시작하기 전에 범위의 시작과 끝을 알아야 합니다. 낮음과 높음이라고 합시다.
Low = 0 High = n-1
이제 검색 값 K를 하한과 상한의 중앙값에 있는 요소와 비교합니다. K 값이 크면 하한을 늘리고 그렇지 않으면 상한을 줄입니다.
위 이미지를 참조하면 하한은 0이고 상한은 9입니다.
하한과 상한의 중앙값은 (lower_bound + upper_bound) / 2 =4입니다. 여기서 a[4] =4입니다. 값 4>2, 검색하려는 값입니다. 따라서 4를 초과하는 요소는 분명히 2보다 크므로 4를 초과하는 요소에 대해 검색을 수행할 필요가 없습니다.
따라서 배열의 상한선을 항상 요소 4의 위치로 떨어뜨릴 수 있습니다. 이제 다음 값을 사용하여 동일한 배열에서 동일한 절차를 따릅니다. -
Low: 0 High: 3
낮음> 높음이 될 때까지 이 절차를 재귀적으로 반복합니다. 반복에서 [mid]=key를 얻으면 mid 값을 반환합니다. 이것은 배열에서 키의 위치입니다. 키가 배열에 없으면 -1을 반환합니다.
예시
int binarySearch(int low,int high,int key){
while(low<=high){
int mid=(low+high)/2;
if(a[mid]<key){
low=mid+1;
}
else if(a[mid]>key){
high=mid-1;
}
else{
return mid;
}
}
return -1; //key not found
}