이진 검색 알고리즘(binary search algorithm)
오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.
장점: 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다.
단점: 정렬된 리스트에만 사용할 수 있다.
작동 원리
[1, 2, 3, 4, 6, 11, 20, 35, 40] 의 정렬된 배열이 있다고 가정하자.
이 중 20을 찾으려고 한다.
1. 우선 가운데 값인 6을 선택한다.
2. 찾으려고 하는 수인 20은 6보다 크다. 그러므로 6보다 작은 값은 과감히 버리자!
3. 남은 배열은 [11, 20, 35, 40]
4. (이 배열에서 다시 1번-2번을 반복한다) 가운데 값인 20을 선택한다.
5. 찾으려고 하는 수인 20과 일치하므로 종료!
이를 자바 코드로 구현하면 다음과 같다.
public int binarySearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
int mid = 0;
while (start <= end) {
mid = (start + end) / 2;
if (target == arr[mid]) {
return mid;
}else if (arr[mid] < target) {
start = mid + 1;
}else if (target < arr[mid]) {
end = mid - 1;
}
}
throw new NoSuchElementException("can't find target.");
}탐색 종료 조건은 '원하는 값을 찾기' 혹은 '더이상 탐색할 배열이 존재하지 않음'이다.
첫번째 조건은 앞선 작동원리에서처럼 원하는 값을 찾는다면 더이상 탐색할 필요가 없기 때문에 간단하다.
두번째 조건은 탐색을 통해 찾으려는 수와 가장 가까운 값을 찾았으나 더이상 비교할 대상이 남지 않은 경우이다.
예를 들어 위 작동원리의 배열 [1, 2, 3, 4, 6, 11, 20, 35, 40]에서 22를 찾으려고 할 때,
탐색 과정을 거쳐 [35, 40]의 배열이 남은 상황에서 22는 35보다 작으므로 배열의 좌측을 탐색해야 하나, 더이상 배열이 남지 않았다. 그러므로 배열에 원하는 수가 없다는 결론과 함께 탐색은 종료된다.
시간복잡도
이름에서 알 수 있듯 binary, 원소의 개수가 반 씩 줄어드는 형상이다.
위 배열에서는 원소의 개수가 9개-4개-2개-... 로 줄어든다.
따라서 n=2^k, k=log2n
> 시간 복잡도는 O(logN)
