이진 검색 (정의, 특징, 간단예시)

정의

 

이진 검색(이분 검색)은 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘이다. 전체 리스트를 중앙값 기준으로 둘로 나누는 과정을 반복해서 찾으려는 값과 비교하는 방식이다.

 

출처: 위키피디아

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

 

특징

 

• 이미 정렬이 된 데이터에만 적용이 가능하다
• 데이터의 중앙값과 찾으려는 값을 비교하는 과정을 반복한다
• 검색이 반복될 때마다 값을 찾을 확률이 두 배가 되어 속도가 빠르다
• 데이터 중앙값 = (최댓값 + 최솟값) / 2

 

예시

 

다음 리스트에서 이진 검색을 사용하여 값 J를 찾는다면, 총 몇 번의 비교를 해야 하는가?

A B C D E F G H I J K L M N O P

 

먼저 리스트를 순서대로 번호를 매겨 준다. (A = 1, B = 2,..., P = 16)

찾으려는 값은 J = 10번이 된다

 

1)

첫 번째 비교: 중앙값 = (1 + 16) / 2 = 8.5 -> 8로 내림

8와 비교해서 10이 더 크므로, 찾으려는 값은 중앙값 8 와 최댓값 16 사이에 있다.

I (9) ~ P (16) 리스트에서 다시 J를 검색한다.

 

2)

두 번째 비교: 중앙값 = (9 + 16) / 2 = 12.5 -> 12로 내림

12와 비교해서 10이 더 작으므로, 찾으려는 값은 중앙값 12와 최솟값 9 사이에 있다.

I (9) ~ K (11) 리스트에서 다시 J를 검색한다.

 

3)

세 번째 비교: 중앙값 = (9 + 11) / 2 = 10

10은 우리가 찾으려는 값의 번호와 일치하여, 검색에 성공하였다.

 

이로서 세 번의 비교를 하여 이진 검색으로 J를 찾게 된다.