[Algorithm] 검색 알고리즘 : 이진 검색 알고리즘

이진 검색 알고리즘이란?

오름차순으로 정렬된 리스트에서 특정값을 찾는 알고리즘이다. 오름차순으로 정렬되어야 하는 이유는 중앙값을 기준으로 특정값이 어디 있는지 판단하기 때문이다. 찾고자 하는 값이 중앙값보다 크면 뒤쪽 절반에서 값을 찾고, 작으면 앞쪽 절반에서 값을 찾는 과정을 반복한다. 즉, 검색 범위를 절반씩 좁혀나간다. 하나씩 비교해 가며 값을 찾는 선형 검색보다 훨씬 효율적이다.

동작 방식

1. 배열의 중앙값과 검색값을 비교한다.
  1) 검색값과 중앙값이 같으면  검색을 종료한다.
  2) 검색값이 중앙값보다 작으면 중앙값을 기준으로 배열의 왼쪽 구간을 검색한다.
  3) 검색값이 중앙값보다 크면 중앙값을 기준으로 배열의 오른쪽 구간을 검색한다.

2. 위 과정을 값을 찾거나 더 이상 검색할 범위가 존재하지 않을 때 까지 반복한다.
  1) 검색값 == 중앙값 (검색 성공)
  2) 검색할 배열의 첫 번째 인덱스 == 검색할 배열의 마지막 인덱스 (검색 실패)

구현

public class search {
	static int binarySearch(int[] array, int searchValue) {
		int startIndex = 0;
		int endIndex = array.length - 1;
		
		while (startIndex <= endIndex) {
			int midIndex = (startIndex + endIndex)/2;
			if (array[midIndex] == searchValue) {
				return midIndex;
			} else if (array[midIndex] < searchValue) {
				startIndex = midIndex + 1;
			} else {
				endIndex = midIndex - 1;
			}
		}
		
		return -1;
	}
}

앞서 언급했다시피 이진 검색 알고리즘은 오름차순 정렬을 전제로 한다. 만약 배열이 오름차순으로 정렬되어 있지 않다면 검색값이 중앙값보다 크다고 해서 검색값이 배열의 왼쪽 구간에 있을 것이라는 보장이 없다. 그래서 검색값이 오른쪽에 있는 경우, 검색값이 배열 내에 존재함에도 불구하고 검색은 실패할 것이다. 검색값이 중앙값보다 작은 경우도 마찬가지다. 이러한 이유로 이진 검색 알고리즘을 사용하기 위해선 반드시 배열이 오름차순으로 정렬되어 있어야 한다.

 

시간 복잡도

이진 검색은 매 시행마다 검색할 자료의 개수가 절반으로 줄어든다. 최초 입력된 자료의 개수가 N이고 시행 횟수가 k라면 남아있는 자료의 개수는 다음과 같다.

$(\frac{1}{2})^k*N$

검색을 반복한 끝에 찾고자 하는 값이 없는 경우, 그러니까 최악의 경우 자료는 1개가 남는다.

$(\frac{1}{2})^k*N \approx 1$

그리고 양변에 $2^k$ 를 곱하고 2를 밑으로 하는 로그를 취해서 k 값을 표현하면 다음과 같다.

$2^k*(\frac{1}{2})^k*N \approx 2^k*1$

$N \approx 2^k$

$k \approx log_{2}N$

k는 시행 횟수이므로 자료 개수 N에 따른 시행 횟수는 $log_{2}N$ 이다. 그리고 이 식은 최악의 경우로부터 유도해냈으므로 빅오 표기법으로 표기할 수 있다. 따라서 이진 검색 알고리즘의 시간 복잡도는 O$(logN)$ 이다.

참고: https://jwoop.tistory.com/9