[Algorithm] 이분 탐색 (Binary Search)

1. 탐색(Search)이란?

• 수열과 탐색 대상 X가 주어졌을 때,

• X가 존재하는 지?
• X[이하, 미만, 이상, 초과]의 원소는 몇 개가 있는지?
• X랑 가장 가까운 원소는 무엇인지?
• 모두 시간복잡도 O(N)을 가진다.

 

2. 이분 탐색 (Binary Search)

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

• 1) 임의의 M번 인덱스에 있는 A[M]이 X보다 크다면, A[M...N]은 전부 X보다 크다.
• 2) 임의의 M번 인덱스에 있는 A[M]이 X보다 작다면, A[1...M]은 전부 X보다 작다.
• * 오름차순 정렬이기 때문에 생기는 성질! 정렬이 아니라면 불가능하다.

(1) 이분탐색 과정

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

• Result=6 이므로
  • A[6]은 X이하 중 제일 큰 값이고
  • A[7]은 X보다 큰 값일 것이다.
  • X 이하의 숫자가 6개 인 것도 알 수 있다.

(2) 시간 복잡도

O(log N)

• A[M]과 X를 한 번 비교할 때마다 [L, R] 구간이 절반씩 좁아집니다.
• 구간의 길이:= N -> N/2 -> N/4 -> ... -> 1 의 순서로 구간이 점점 좁아진다.
• "총 비교 횟수"는 "구간의 변화 횟수"인 O(log N) 만에 원하는 값을 탐색한다.
• ex) N = 100,000 (10만)
  • 10만 >>>> log(100,000) = 대략 16

(3) 자주 하는 실수

• 입력된 배열에 바로 이분 탐색을 하는데, 정렬을 하지 않는 경우
• L, R, M, Result 변수의 정의를 헷갈려서 부등호 등을 잘못 쓰는 경우
• L, R 범위를 잘못 설정하거나 Result의 초기값을 잘못 설정하는 경우

 

3. 이분 탐색 구현

• 배열 B에서 X 미만의 수(X 보다 작은 수) 중 제일 오른쪽 인덱스를 return 하는 함수

// 배열 B에서 X 미만의 수(X 보다 작은 수) 중 제일 오른쪽 인덱스를 return 하는 함수
// 그런 게 없다면 L - 1을 return 한다.
static int binarySearch(int[] B, int L, int R, int X) {
    int result = L-1;
    while (L <= R) {
        int mid = (L + R) / 2;
        if(B[mid] < X) {
            result = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
    return result;
}