알고리즘) 이분탐색 및 결정 알고리즘

이분 탐색(Binary Search)

 탐색(search) 기법 중 하나로, 정렬된 배열에서 찾고자하는 값을 탐색할 때 그 범위를 두 부분으로 나누어(=이분) 탐색하는 방법이다. 탐색하고자 하는 범위를 계속해서 줄여감으로써 시간 효율성을 O(logN)까지 올릴 수 있다.

탐색 범위를 줄이는 방법은 다음과 같다.

1. 범위의 가장 중앙 인덱스(mid)의 값과 찾고자 하는 값을 비교한다.
2. 찾고자 하는 값이 해당 인덱스(mid) 값보다 클 경우 범위는 해당 인덱스(mid)의 바로 뒤(mid + 1)부터 탐색 범위의 마지막 인덱스(처음에는 끝 인덱스)까지이다.
3. 다시 정의된 범위에서 가장 중앙 인덱스의 값과 비교한다. (mid 값 변경)
4. 찾고자 하는 값이 중앙 인덱스 값보다 작을 경우 범위는 탐색 범위의 시작 인덱스부터 해당 인덱스(mid)까지로 줄어든다.

 위와 같은 방식으로 계속해서 범위를 두 부분으로 나누어 중앙값보다 찾으려는 값이 큰지 작은지에 따라 범위를 반씩 줄여나가는 방식이다.

중요 포인트

 요소를 탐색하기 전에 배열이 정렬되어 있어야 한다는 점, 양 끝단의 인덱스를 변수화(left 혹은 min, right 혹은 max)하여 항상 두 인덱스의 중앙값(mid)을 확인한다는 점. 요소가 찾고자 하는 값보다 크거나 작을 때는 위의 두 변수(left, right)가 가리키는 인덱스를 변경시켜 mid값을 검증하는 것을 반복한다는 점이 있다.

 

주요 개념

UpperBound와 LowerBound 개념을 결부지으면 왜 범위를 좁힐 때 찾고자 하는 값보다 클 경우에는 lt를 mid값으로 변경하고, 찾고자 하는 값과 같거나 더 작은 경우에는 rt 값을 mid - 1로 변경하는지 이해할 수 있다.

• 상계(UpperBound) : 찾고자 하는 값을 초과한 값이 처음 등장하는 위치
• 하계(LowerBound) : 찾고자 하는 값 이상의 값이 나타나기 시작하는 위치

 

예제

 아래의 배열 A에서 a의 인덱스를 찾는다고 생각해보자. (배열 A의 원소들은 중복되지 않으며, a와 A의 원소들은 모두 4 byte 정수의 범위 내의 값이라고 가정한다.)

int a = 9;
int[] A = {8, 4, 1, 3, 9, 10, 11, 5, 4, 2};

 우선 배열 A는 정렬되어 있지 않기 때문에, 이를 정렬하는 과정이 필요하다. 이 때, 이 문제가 정렬 문제였다면 제시된 방법 혹은 가장 상황에 가장 효율적인 방법으로 정렬하겠지만, 문제가 이분 탐색을 묻는 문제라면 이 부분은 기존에 제공되는 api를 이용해 간단하게 구현하는 것이 좋다.

Arrays.sort(A); // A = {0, 1, 2, 3, 4, 5, 8, 9, 10, 11};

 처음에 정렬된 A에서 탐색하려하는 범위는 A[0] ~ A[A.length - 1] 이기 때문에, 아래와 같이 인덱스를 값으로 가지는 변수 둘을 정의하여 각각의 값을 0과 10(= A.length - 1)으로 둔다. 탐색하는 범위는 계속해서 줄어들 것이기 때문에 결국에는 lt와 rt가 같아지고, 그 이후에는 lt가 rt가 커지게 될 것이다.(lt가 증가하거나, rt가 감소하거나) 그래서 while문은 모든 탐색이 끝날 때 까지라는 의미로 lt ≤ rt인 동안 실행되도록 한다.

cf. 범위의 중앙 인덱스(mid)는 while 루프 내에서 lt와 rt가 변경됨에 따라 계속해서 바뀌므로 루프문 안에 작성하였다.

A[mid]값이 a 보다 클 경우를 보자. 배열 A가 정렬된 상태임을 감안하면 중앙 인덱스의 값이 a 보다 크다는 말은 A[mid] 이후의 값들은 당연히 a 보다 크다는 말이 된다. 때문에 굳이 탐색할 필요가 없는 것이다. 결론적으로는 나뉜 두 범위 중 앞 범위를 선택하게 됨으로 탐색 범위의 마지막 인덱스(rt)를 mid 보다 1 작은 수로 변경한다.

 A[mid]값이 a 보다 작은 경우는 위와 반대의 경우로 이해하기 쉬울 것이라 생각되어 생략한다.

 A[mid]값이 a와 같은 경우에는 탐색하고자 하는 값을 찾았으므로 탐색을 끝내도 된다. (지금은 배열 A가 a값을 가지고 있는지 여부만 판단하기 때문에 존재함을 확인하면 루프가 끝날 수 있다.)

int lt = 0, rt = A.length - 1;
while (lt <= rt) {
    int mid = (lt + rt) / 2;

    if (a > A[mid]) lt = mid + 1;
    else if (a < A[mid]) rt = mid - 1;
    else return mid;
}

 

---

결정 알고리즘

 이분 탐색(이진 탐색)만 요구하는 간단한 문제도 있지만, 조금만 난이도를 올려도 반드시 결정 알고리즘이 결부되어 나온다. 조건에 일치하는지 예, 아니오로 결정할 수 있는 문제에 사용하는 것 같다. 주로 조건에 해당하는 값의 최솟값, 최댓값을 구하는 문제로 나온다. 단순한 이분 탐색 문제는 특정 값의 존재 유무, 특정 값의 인덱스를 찾는 정도라면 결정 알고리즘 문제는 특정 조건에 일치하는 상황들이 여러 경우 나오고, 이 경우들 중 또 다른 특정 조건(주로 최솟값, 최댓값)인 경우를 출력하게 하는 문제가 많다.

문제 예시

• 뮤직비디오 (소스 코드)
• 마구간 (소스 코드)