정렬되어 있는 배열에서 특정한 값을 O(log N)에 찾는 알고리즘
이진탐색 알고리즘은 탐색범위의 중간값과의 비교를 통해, $\frac12$씩 탐색범위를 계속 좁혀가는 방식으로 탐색한다.
성능
한번의 연산마다 $\frac12$씩 탐색범위를 줄여 탐색범위를 1로 만드는 과정이다
n개의 데이터의 탐색범위를 1로 만들기 위해 k번의 비교연산을 한다고 생각해보자
아래와 같은 수식으로 표현된다
n개의 데이터에서, 1개 데이터 찾기위한 연산횟수 k
$$n\times\frac12^k = 1$$
$$n = 2^k$$
$$log_2n = k$$
따라서, n개의 데이터에서 1개의 데이터를 찾기위한 이진탐색의 연산횟수는$log_2n = k$번이며, 이것이 빅-오 노테이션 성능이다.
구체적인 탐색 과정
다음의 데이터에서 46을 탐색하는 과정을 살펴보자
1. 중간 데이터를 구한다.
현재 탐색범위는 0 ~ 11 index 이다
중간 인덱스는 처음과 끝 인덱스의 평균값으로 구한다
$\frac{0+11}{2}={5}$ 이므로, 5 index가 중간 데이터이다
2. 중간데이터와 46을 비교해 탐색범위를 다시 정한다
46이 더 크다면, 중간데이터를 포함한 왼쪽 데이터들을 버릴 수 있다.
46이 더 작다면, 중간데이터를 포함한 오른쪽 데이터들을 버릴 수 있다.
3. 1,2번 과정을 반복한다
댓글