이진 검색은 정렬된 배열에서 작동합니다. 값은 배열의 중간 요소와 비교됩니다. 같음이 발견되지 않으면 값이 없는 절반 부분이 제거됩니다. 같은 방법으로 나머지 반쪽도 검색합니다.
다음은 배열의 중간 요소입니다. 62를 찾아야 한다고 가정해 봅시다. 그러면 왼쪽 부분이 제거되고 오른쪽 부분이 검색됩니다 -
다음은 이진 검색의 복잡성입니다. -
| 최악의 성능 | O(로그 n) |
| 최상의 성능 | O(1) |
| 평균 실적 | O(로그 n) |
| 최악의 공간 복잡성 | O(1) |
예시
이진 검색을 구현하는 방법을 살펴보겠습니다 -
public static object BinarySearchDisplay(int[] arr, int key) {
int minNum = 0;
int maxNum = arr.Length - 1;
while (minNum <=maxNum) {
int mid = (minNum + maxNum) / 2;
if (key == arr[mid]) {
return ++mid;
} else if (key < arr[mid]) {
max = mid - 1;
}else {
min = mid + 1;
}
}
return "None";
}