이진탐색

수열에서의 탐색이란

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

• X가 존재하는지?
• X(이하,미만,이상,초과) 의 원소는 몇 개가 있는지?
• X랑 가장 가까운 원소는 무엇인지?

를 의미합니다.

만약, 정렬이 되어있는 수열이라면

더 빠르게 탐색할 수 있는 방법이 있는데, 이진 탐색이다.

이진 탐색

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

O(log N)

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

1. 임의의 M번 인덱스에 있는 A[M] 값이 X 보다 크다면, A[M...N] 은 전부 X 보다 크다.
2. 임의의 M번 인덱스에 있는 A[M] 값이 X 보다 작다면, A[1...M] 은 전부 X 보다 작다.

주의 : 이진 탐색을 하려면 오름차순 정렬이 되어야만 한다.

이분 탐색

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

N 이 10만 -> log(10만) = 16 만에 탐색이 가능

자주 하는 실수

3위 : L,R 범위를 잘못 설정하거나 Result 의 초기값을 잘못 설정하는 경우
2위 : L,R,M,Result 변수의 정의를 헷갈려서 부등호 잘못 쓰는 경우
1위 : 이분 탐색을 하는데, 정렬을 하지 않는 경우

코드

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