똑똑한 코드 작성을 위한 실전 알고리즘

63

2

장

알고리즘 분석

이 장에서는 많은 이론적 자료를 다뤘으며 이제 이러한 개념을 실제 사용에 적용할 때다. 다음

절에서는 컴퓨터 과학의 최적 탐색 알고리즘인 이진 배열 탐색

Binary

Array

Search

을 살펴본다. 이것

이 효율적인 이유를 설명하면서 새로운 복잡도 클래스

O

(

log

N

)을 소개한다.

2.7

이진 배열 탐색

[그림

2

-

4

]를 보자. 왼쪽부터 오름차순으로 숫자 일곱 개를 쓰고 각 문 뒤에 하나씩 숨겼다. 문

을 하나씩 열어서 목푯값인

643

을 찾거나 혹은

643

이 문들 뒤에 없다는 것을 증명하려면 최소

몇 개의 문을 열어봐야 하는가? 맨 왼쪽부터 시작해서

643

이나 더 큰 수(애초에 해당 숫자가

문 뒤에 없다는 의미)를 찾을 때까지 문을 하나씩 열어볼 수 있다. 하지만 운이 나쁘면 문

7

개

를 다 열어봐야 할 수도 있다. 이런 탐색 전략은 문 뒤에 있는 수가 오름차순이라는 사실을 이

용하지 않는다. 이 방법 대신 문을

3

개 이상 열지 않고 문제를 해결할 수 있다. 가운데 있는

4

번 문부터 열어보자.

그림

2-4

운명의 문!

4

번 문 뒤에 숨겨진 수는

173

이다.

643

을 찾고 있으므로

4

번 문 왼쪽에 있는 문은 모두 무시

할 수 있다 (뒤에 있는 수들이 모두

173

보다 작을 것이므로 ). 다음으로

6

번 문을 열어

900

이

나왔다. 좋다. 이제 ...