주어진 데이터들에서 특정 데이터를 찾으려면 어떻게 해야할까?
주어진 데이터가 N개라면 최대 N개의 데이터가 특정 데이터인지 비교하며 찾아야 할 것이다. 이 방법이 그렇게 나쁘게 보이진 않지만 주어진 데이터가 정렬이 되어있다면 더욱 빠르게 특정 데이터를 찾는 방법이 있다.
1부터 100까지의 숫자 중 상대방이 하나의 숫자를 고르고 내가 그 숫자를 맞춰야하는 상황에서 상대방이 내가 숫자를 말하면 자기가 생각한 숫자가 그 수보다 큰지 작은지 알려준다고 할 때 1부터 100까지 순서대로 말하는 사람은 없을 것이다. 50을 말해보고 50보다 작다면 25를 50보다 크다면 75를 말하며 빠르게 숫자를 찾아나갈 것이다. 오늘 주제인 이분 탐색도 이와 같은 원리이다.
1. 이분 탐색 (Binary Search)
이분 탐색, 이진 탐색, 이분 검색, 이진 검색 등 다양한 이름으로 불리는 이분 탐색(Binary Search)은 위키백과에 따르면 오름차순으로 정렬된 리스트에서 특정한 값(target)의 위치를 찾는 알고리즘으로 나와있다.
정렬된 리스트에서 탐색하려는 구간의 시작 인덱스를 left, 끝 인덱스를 right, 구간의 중간 인덱스를 mid, 찾고자 하는 값을 target이라고 했을 때, 리스트의 mid에 위치한 값과 target을 비교하여 target이 더 크면 탐색 범위를 (mid + 1)부터 (right)으로 설정하고, target이 더 작으면 탐색 범위를 (left)부터 (mid - 1)로 설정한 뒤 다시 해당 범위의 mid에 위치한 값과 target을 비교하는 과정을 반복하는 것이 기본 원리이다. 매번 탐색 범위를 절반으로 줄일 수 있는 것은 정렬이 되어있어서 버리는 절반에 target이 없는 것을 확신할 수 있기 때문으로 리스트의 길이가 N일 때 O(log N)의 시간복잡도로 target을 찾을 수 있다. 이분 탐색은 정렬과 O(1)로 특정 인덱스에 접근할 수 있는 선형 자료구조가 핵심으로 내림차순으로 정렬이 되어있거나 리스트 대신 배열에 적용해도 무방하다. 특정 인덱스 접근에 O(N)의 시간복잡도가 소요되는 LinkedList는 이분 탐색 구현은 가능하지만 O(log N)의 시간복잡도로 탐색할 수 없다.
자바에서는 배열과 리스트에 대한 이분 탐색 메서드를 기본으로 제공하며 배열은 Arrays.binarySearch, 리스트는 Collections.binarySearch 메서드로 탐색이 가능하다. 두 가지 모두 오버로딩된 메서드들이 존재하므로 잘못 사용하지 않게 주의해야 한다.
이분 탐색의 구현은 반복문을 활용한 구현과 재귀를 활용한 구현 크게 두 가지가 있다. 두 방식 모두 탐색 범위의 양 끝 인덱스를 저장하는 포인터가 필요하고 왼쪽 포인터가 오른쪽 포인터보다 오른쪽에 위치하는 순간(탐색 구간이 없음) 탐색을 종료하면 된다. 탐색 과정은 두 포인터의 중간에 해당하는 위치를 계산하고 이 위치에 있는 값이 target이면 탐색 종료, target이 아니면 포인터 위치 변경이 이루어진다. 끝까지 target을 찾지 못했으면 못 찾았다는 의미로 음수를 반환한다.(인덱스는 음수가 될 수 없으므로)
// 반복문으로 구현한 이분 탐색
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] < target) left = mid + 1;
else if (arr[mid] > target) right = mid - 1;
else return mid;
}
// target을 못 찾으면 음수 반환
return -1;
}
// 재귀로 구현한 이분 탐색
public static int binarySearchRecursive(int[] arr, int target) {
return binarySearch(arr, 0, arr.length - 1, target);
}
// 재귀로 구현한 이분 탐색
public static int binarySearch(int[] arr, int left, int right, int target) {
// target을 못 찾으면 음수 반환
if (left > right) return -1;
int mid = (left + right) / 2;
if (arr[mid] < target) return binarySearch(arr, mid + 1, right, target);
else if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target);
else return mid;
}
이건 내가 구현한 이분 탐색으로 int형 데이터를 담는 배열에 대한 이분 탐색을 구현한 것이고 재귀로 구현한 이분 탐색은 추후 함수형 인터페이스 적용을 위해 2단계로 나누었다. 이분 탐색에서 실수하기 가장 쉬운 부분이 탐색 범위를 나타내는 양 끝 포인터가 동일할 때도 구간 1이 존재하는 상황으로 탐색을 진행해야한다는 부분인데 이점만 주의하면 간단하게 구현할 수 있다. 이렇게 구현하면 배열에서 target이 위치한 인덱스를 O(log N)의 시간복잡도로 찾을 수 있고 target이 존재하지 않으면 -1을 반환 받아서 탐색 실패 여부도 알 수 있다.
2. Lower Bound 이분 탐색, Upper Bound 이분 탐색
이분 탐색을 수행하려는 배열, 리스트가 정렬은 되어 있지만 중복된 값이 존재하는 상태일 때 target의 위치는 여러 곳이 될 수 있다. 정확히는 특정 구간이 전부 후보가 되고 탐색 범위의 중간이 이 구간에 들어오면 값을 반환하게 될 것이다. target의 위치는 맞으니 문제는 없지만 중복된 값이 존재하는 상황에서 target을 찾고자 할 때 궁금한 내용은 보통 아래 4가지 중 하나일 것이다.
- target 이상인 값이 등장하는 가장 작은 인덱스
- target 초과인 값이 등장하는 가장 작은 인덱스
- target 이하인 값이 등장하는 가장 큰 인덱스
- target 미만이 값이 등장하는 가장 큰 인덱스
이때 이분 탐색을 응용하면 이러한 문제를 해결할 수 있는데 target 이상인 값이 등장하는 가장 작은 인덱스를 찾는 방법을 Lower Bound 이분 탐색, target 초과인 값이 등장하는 가장 작은 인덱스를 찾는 방법을 Upper Bound 이분 탐색이라고 한다. 두 가지 모두 기존 이분 탐색과 유사하게 구현할 수 있다. target 이하인 값이 등장하는 가장 큰 인덱스는 (Upper Bound 이분 탐색으로 찾은 인덱스 - 1), target 미만이 값이 등장하는 가장 큰 인덱스는 (Lower Bound 이분 탐색으로 찾은 인덱스 - 1)로 구할 수 있다.
Lower Bound 이분 탐색의 경우 target 이상인 값이 등장하는 가장 작은 인덱스를 찾아야 하므로 탐색 범위의 중간에 위치한 값이 target보다 작을 경우 이분 탐색처럼 해당 중간값보다 작거나 같은 인덱스의 값들은 모두 target 보다 작아서 버리면 된다. 다만 탐색 범위의 중간에 위치한 값이 target보다 클 경우 해당 값이 target 이상인 값들 중 가장 인덱스가 작을 수 있으므로 이 인덱스는 구간에 포함해야 한다.
Upper Bound 이분 탐색의 경우 Lower Bound와 거의 유사하며 구간의 이동 조건만 달라진다. target 초과인 값이 등장하는 가장 작은 인덱스를 찾아야하므로 탐색 범위의 중간에 위치한 값과 target이 동일할 때도 왼쪽 포인터를 이동시키면 된다.
Lower Bound 이분 탐색과 Upper Bound 이분 탐색 모두 left는 mid + 1, right는 mid로 이동하는 과정을 반복하는데 이상 또는 초과인 값은 항상 존재할 수 밖에 없으므로 left == right가 되는 순간 탐색을 종료하면 되고 left 또는 right 중 아무 값이나 반환하면 된다. left == right에서도 탐색을 진행하면 무한 루프에 빠질 수 있다. 추가로 이분 탐색과 달리 right의 초기 위치를 (탐색하려는 구간의 끝 인덱스 + 1)로 설정해서 탐색 구간에서 가장 큰 값보다 target이 클 경우도 인덱스 값이 일관되게 처리한다.
// target 이상인 값들 중 최소 인덱스 위치를 찾는 이분 탐색
public static int binarySearchLowerBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return right;
}
// target 초과인 값들 중 최소 인덱스 위치를 찾는 이분 탐색
public static int binarySearchUpperBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] <= target) left = mid + 1;
else right = mid;
}
return right;
}
이건 내가 구현한 Lower Bound 이분 탐색과 Upper Bound 이분 탐색으로 int형 데이터를 담는 배열에 대한 이분 탐색을 구현한 것이다.
3. 이분 탐색 구현 테스트
이렇게 int형 배열에 대한 이분 탐색들을 구현 후 간단한 테스트로 잘 구현됐는지 테스트했다. 테스트는 중복된 값이 없는 배열, 중복된 값이 있는 배열 두 가지를 준비했고 각각 0 부터 9 사이의 숫자가 임의로 오름차순으로 정렬된 채로 배치시켰다.
import java.util.Arrays;
public class UnitTest {
@FunctionalInterface
public interface BinarySearchFunction {
int apply(int[] arr, int target);
}
public static void main(String[] args) {
int[] arr = {0, 1, 2, 4, 5, 6, 8, 9};
int[] arr2 = {1, 3, 3, 3, 6, 8, 9, 9};
print("arr", arr);
print("arr2", arr2);
print("Arrays.binarySearch(arr, num)", arr, Arrays::binarySearch);
print("Arrays.binarySearch(arr2, num)", arr2, Arrays::binarySearch);
print("binarySearch(arr, num)", arr, BinarySearch::binarySearch);
print("binarySearch(arr2, num)", arr2, BinarySearch::binarySearch);
print("binarySearch(arr, 0, arr.length - 1, num)", arr, BinarySearch::binarySearchRecursive);
print("binarySearch(arr2, 0, arr2.length - 1, num)", arr2, BinarySearch::binarySearchRecursive);
print("binarySearchLowerBound(arr, num)", arr, BinarySearch::binarySearchLowerBound);
print("binarySearchLowerBound(arr2, num)", arr2, BinarySearch::binarySearchLowerBound);
print("binarySearchUpperBound(arr, num)", arr, BinarySearch::binarySearchUpperBound);
print("binarySearchUpperBound(arr2, num)", arr2, BinarySearch::binarySearchUpperBound);
}
public static void print(String message, int[] arr) {
System.out.println(message);
System.out.print("index");
for (int i = 0; i < arr.length; i++) {
System.out.printf("%3d", i);
}
System.out.println();
System.out.print("value");
for (int i = 0; i < arr.length; i++) {
System.out.printf("%3d", arr[i]);
}
System.out.println("\n");
}
public static void print(String message, int[] arr, BinarySearchFunction function) {
System.out.println(message);
for (int num = 0; num <= 10; num++) {
int result = function.apply(arr, num);
if (result >= 0) System.out.printf("%3d", result);
else System.out.printf("%3s", "X");
}
System.out.println("\n");
}
}
테스트 파일은 함수형 인터페이스를 활용해 출력 메서드를 작성하는 방식으로 구현했다.
arr
index 0 1 2 3 4 5 6 7
value 0 1 2 4 5 6 8 9
arr2
index 0 1 2 3 4 5 6 7
value 1 3 3 3 6 8 9 9
Arrays.binarySearch(arr, num)
0 1 2 X 3 4 5 X 6 7 X
Arrays.binarySearch(arr2, num)
X 0 X 3 X X 4 X 5 6 X
binarySearch(arr, num)
0 1 2 X 3 4 5 X 6 7 X
binarySearch(arr2, num)
X 0 X 3 X X 4 X 5 6 X
binarySearch(arr, 0, arr.length - 1, num)
0 1 2 X 3 4 5 X 6 7 X
binarySearch(arr2, 0, arr2.length - 1, num)
X 0 X 3 X X 4 X 5 6 X
binarySearchLowerBound(arr, num)
0 1 2 3 3 4 5 6 6 7 8
binarySearchLowerBound(arr2, num)
0 0 1 1 4 4 4 5 5 6 8
binarySearchUpperBound(arr, num)
1 2 3 3 4 5 6 6 7 8 8
binarySearchUpperBound(arr2, num)
0 1 1 4 4 4 5 5 6 8 8
결과는 위와 같이 나왔는데 예상대로 잘 출력된 것을 볼 수 있었다.
4. 이분 탐색 성능 테스트
ArrayList와 LinkedList에 대한 Collections.binarySearch 성능 테스트와 내가 구현한 이분 탐색, Arrays.binarySearch에 대한 성능 테스트를 간단하게 진행했다.
import java.util.*;
public class PerformanceTest {
public static void main(String[] args) {
List<Integer> arrayList = new ArrayList<>(Arrays.asList(0, 1, 2, 4, 5, 6, 8, 9));
List<Integer> linkedList = new LinkedList<>(Arrays.asList(0, 1, 2, 4, 5, 6, 8, 9));
int stress = 1_000_000_000;
test("Collections.binarySearch(arrayList, num)", stress, arrayList);
test("Collections.binarySearch(linkedList, num)", stress, linkedList);
}
public static void test(String message, int T, List<Integer> list) {
System.out.println(message);
long start = System.nanoTime();
for (int tc = 1; tc <= T; tc++) {
for (int num = 0; num <= 10; num++) {
int result = Collections.binarySearch(list, num);
}
}
long end = System.nanoTime();
System.out.printf("실행시간: %.3fs\n\n", (end - start) / 1_000_000_000.0);
}
}
// 결과
Collections.binarySearch(arrayList, num)
실행시간: 48.149s
Collections.binarySearch(linkedList, num)
실행시간: 127.227s
8개의 원소를 갖는 두 리스트에서 0부터 10까지의 수가 존재하는지 탐색을 10억번 진행하는 상황으로 테스트를 하려고 했고 내가 작성한 테스트에서는 제법 실행시간 차이가 나는 것을 볼 수 있었다.
import java.util.Arrays;
public class PerformanceTest2 {
@FunctionalInterface
public interface BinarySearchFunction {
int apply(int[] arr, int target);
}
public static void main(String[] args) {
int[] arr = {0, 1, 2, 4, 5, 6, 8, 9};
int stress = 2_000_000_000;
test("Arrays.binarySearch(arr, num)", stress, arr, Arrays::binarySearch);
test("binarySearch(arr, num)", stress, arr, BinarySearch::binarySearch);
test("binarySearch(arr, 0, arr.length - 1, num)", stress, arr, BinarySearch::binarySearchRecursive);
}
public static void test(String message, int T, int[] arr, BinarySearchFunction function) {
System.out.println(message);
long start = System.nanoTime();
for (int tc = 1; tc <= T; tc++) {
for (int num = 0; num <= 10; num++) {
int result = function.apply(arr, num);
}
}
long end = System.nanoTime();
System.out.printf("실행시간: %.3fs\n\n", (end - start) / 1_000_000_000.0);
}
}
// 결과
Arrays.binarySearch(arr, num)
실행시간: 50.125s
binarySearch(arr, num)
실행시간: 62.081s
binarySearch(arr, 0, arr.length - 1, num)
실행시간: 88.741s
8개의 원소를 갖는 배열에서 0부터 10까지의 수가 존재하는지 탐색을 20억번 진행하는 상황으로 테스트를 하려고 했고, Arrays.binarySearch, 반복문으로 구현한 이분 탐색, 재귀로 구현한 이분 탐색 3가지를 비교해보았다. 자바 내장 메서드가 가장 빠르고 재귀로 구현한 이분 탐색이 가장 느린 것으로 나왔지만 큰 차이까지는 없는 것 같았다.
5. 마무리
이분 탐색은 알고리즘 문제로도 종종 등장하는 유형으로 기본적인 이분 탐색 뿐만 아니라 Lower Bound, Upper Bound, 매개변수 이분 탐색 등 다양한 형태로 등장하고 다른 알고리즘의 적용 과정에서 같이 사용되기도 하는 등 꼭 알아야 하는 유형인 것 같다. 주어진 데이터가 정렬되어 있지 않더라도 특정 데이터를 조회하는 상황이 빈번하면 정렬에 걸리는 추가 시간과 이분 탐색 적용으로 줄이는 시간의 트레이드 오프를 잘 따져보는 것도 중요한 것 같으며 구현에서 실수할 여지가 있어서 충분한 연습이 필요한 것 같다.