[Algorithm] 이분 탐색(Binary Search)

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다.

출처 : https://github.com/rhs0266/FastCampus

 

 

 

탐색

수열과 탐색 대상 x가 주어진 경우

• x가 존재하는가?
• x 이하 or 미만 or 이상 or 초과 하는 원소의 개수는?
• x랑 가장 가까운 원소는 무엇인가?
• ...

 

모든 원소를 보면서 x와 비교를 하는 경우 O(N)의 시간복잡도로 위의 질문을 대답할 수 있다.

 

그런데 만약 정렬이 된 수열이 주어진다면 어떻게 될까? 

정렬된 수열과 탐색 대상 x가 주어진 경우 이분 탐색을 이용하면 더 빠르게 위의 질문을 대답할 수 있다.

 

이분 탐색 (Binary Search)

정렬이 보장되는 배열에서 기준 x를 가지고 범위를 "이분"하면서 탐색하는 방법

 

정렬이 보장된다는 의미는 무엇일까?

• 원소가 공개된 배열을 받아서 정렬한 경우
• 어떤 원소를 가지고 있는 지 모르지만 정렬되어 있다는 사실을 알려준 경우

 

이분 탐색을 사용하면 시간 복잡도 O(log N)으로 해결할 수 있다.

 

 

오름차순 정렬이 된 배열의 특성

• A[M]이 X보다 크면 A[M~마지막]은 전부 X보다 크다.
• A[M]이 X보다 작으면 A[1~M]은 전부 X보다 작다.

 

이 특성을 이용해서 이분 탐색을 진행한다.

• L : 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스
• R : 탐색할 가치가 있는 범위의 오른쪽 끝 인덱스
• Result : 탐색한 X의 위치
• 탐색 목표 : X 이하의 원소 중에 가장 오른쪽에 있는 원소

 

 

 

초기상태

 

1. M = (L+R)/2 = 3. A[M]과 X 비교 -> 15 < 29, result = 3

2. L = M+1 = 4

3. M = (L+R)/2 = 5. A[M]과 X 비교 -> 33 > 29, result = 5

4. R = M-1 = 4

3. M = (L+R)/2 = 4. A[M]과 X 비교 -> 19 < 29, result = 4

4. L = M+1 = 5

 

L > R이 되는 순간 탐색할 구간이 없어지는 것이므로 종료

 

result = 4 이므로 알 수 있는 사실들

• A[4]는 X 보다 작은 값 중 제일 큰 값
• A[5]은 X 보다 큰 값 중 제일 작은 값
• X 이하의 숫자가 4개

 

시간 복잡도 계산

정렬이 되어있다는 가정 하에,

 

A[M]과 X를 한 번 비교할 때마다 탐색 구간이 절반씩 좁아진다.

 

따라서 총 비교 횟수는 구간의 변화 횟수인 O(log N)만에 이분탐색이 가능하다.

 

만약 N이 10만이라면 log(10만)은 약 16이기 때문에 매우 빠르게 탐색이 가능하다.

 

 

 

자주 하는 실수

• 정렬을 하지 않고 이분탐색을 하는 경우
• 부등호 실수
• L, R 범위를 잘못 설정하거나 Result의 초기값을 설정하는 경우