이진 탐색(Binary Search)
- 이진 탐색은 데이터가 정렬되어 있을 때, O(logN)의 시간 복잡도로 목표 데이터를 찾는 알고리즘이다.
- 재귀함수 또는 반복문을 통해 구현할 수 있다.
이진 탐색 동작 과정
- mid(배열의 중간 값)을 target(목표 데이터)과 비교한다.
- mid > target인 경우, 현재 mid보다 작은 데이터들을 대상으로 새로운 mid를 선정하고 다시 target과 비교한다.
- mid < target인 경우, 현재 mid보다 큰 데이터들을 대상으로 새로운 mid를 선정하고 다시 target과 비교한다.
- 위와 같은 과정을 반복하다가 mid == target인 경우, mid를 반환하고 탐색을 종료한다.
이진 탐색 예시 코드
public class BinarySearch {
/**
* @param ints 전체 배열
* @param start 시작 인덱스
* @param end 끝 인덱스
* @param target 목표 데이터
* @return 오름차순 정렬 시, 목표 데이터의 인덱스
*/
public static int recursion(int[] ints, int start, int end, int target) {
if (start > end) {
return -1;
}
int mid = (start + end) / 2; // 중간 지점
if (ints[mid] == target) {
return mid;
} else if (ints[mid] < target) {
return recursion(ints, mid + 1, end, target);
} else {
return recursion(ints, start, mid - 1, target);
}
}
/**
* @param ints 전체 배열
* @param target 목표 데이터
* @return 오름차순 정렬 시, 목표 데이터의 인덱스
*/
public static int iteration(int[] ints, int target) {
int left = 0;
int right = ints.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (ints[mid] == target) {
return mid;
} else if (ints[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
public static void main(String[] args) throws IOException {
int[] numbers1 = {1, 3, 4, 6, 7, 11, 12, 15, 19, 25, 8};
int target11 = 8;
int target12 = 25;
int[] numbers2 = {5, 20, 16, 21, 7, 8, 9, 10, 4};
int target21 = 5;
int target22 = 21;
Arrays.sort(numbers1);
Arrays.sort(numbers2);
System.out.println(recursion(numbers1, 0, numbers1.length, target11)); // 5
System.out.println(iteration(numbers1, target11)); // 5
System.out.println(recursion(numbers1, 0, numbers1.length, target12)); // 10
System.out.println(iteration(numbers1, target12)); // 10
System.out.println(recursion(numbers2, 0, numbers1.length, target21)); // 1
System.out.println(iteration(numbers2, target21)); // 1
System.out.println(recursion(numbers2, 0, numbers1.length, target22)); // 8
System.out.println(iteration(numbers2, target22)); // 8
}
}
LowerBound & UpperBound
- 정렬된 데이터 목록에 중복된 데이터들이 존재한다고 가정하자.
- 이런 상황에서 이진 탐색을 응용하여 LowerBound 및 UpperBound를 구하면 목표 데이터의 개수, 첫 인덱스, 끝 인덱스를 구할 수 있다.
- LowerBound는 목표 데이터 이상의 값이 처음으로 등장하는 인덱스를 의미한다.
- 이진 탐색을 통해 목표 데이터를 탐색한다. arr[mid]는 현재 데이터, target은 목표 데이터이다.
- target 보다 낮은 값은 답이 될 수 없으므로, arr[mid] < target인 경우 left = mid + 1로 범위를 재설정한다.
- target 이상의 값은 답이 될 수 있으므로, arr[mid] >= target인 경우 right = mid로 범위를 재설정한다.
- UpperBound는 목표 데이터를 초과하는 값이 처음으로 나오는 인덱스를 의미한다.
- 이진 탐색을 통해 목표 데이터를 탐색한다. arr[mid]는 현재 데이터, target은 목표 데이터이다.
- target 보다 큰 값이 답이 될 수 있으므로, arr[mid] > target인 경우 right = mid로 범위를 재설정한다.
- target 이하의 값은 답이 될 수 없으므로, arr[mid] <= target인 경우 left = mid + 1로 범위를 재설정한다.
LowerBound & UpperBound 예시 코드
public class LowerBound_UpperBound {
public static int lowerBound(int target, int[] numbers) {
int left = 0;
int right = numbers.length;
while (left < right) { // left == right가 될 경우, out of index가 발생할 수 있다.
int mid = (left + right) / 2;
if (numbers[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static int upperBound(int target, int[] numbers) {
int left = 0;
int right = numbers.length;
while (left < right) { // left == right가 될 경우, out of index가 발생할 수 있다.
int mid = (left + right) / 2;
if (numbers[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
public static void count(int target, int[] numbers) {
int lower = lowerBound(target, numbers);
int upper = upperBound(target, numbers);
int count = upper - lower; // 목표 데이터의 개수
System.out.printf("대상 원소가 %d개 존재합니다.\n", count);
}
public static void main(String[] args) throws IOException {
int[] numbers1 = {1, 1, 2, 3, 4, 5, 5, 7, 10, 12};
int target11 = 1;
int target12 = 5;
int[] numbers2 = {2, 3, 4, 6, 6, 6, 7, 10, 11};
int target21 = 11;
int target22 = 6;
Arrays.sort(numbers1);
Arrays.sort(numbers2);
System.out.println(lowerBound(target11, numbers1)); // 0
System.out.println(upperBound(target11, numbers1)); // 2
count(target11, numbers1); // 대상 원소가 2개 존재합니다.
System.out.println(lowerBound(target12, numbers1)); // 5
System.out.println(upperBound(target12, numbers1)); // 7
count(target12, numbers1); // 대상 원소가 2개 존재합니다.
System.out.println(lowerBound(target21, numbers2)); // 8
System.out.println(upperBound(target21, numbers2)); // 9
count(target21, numbers2); // 대상 원소가 1개 존재합니다.
System.out.println(lowerBound(target22, numbers2)); // 3
System.out.println(upperBound(target22, numbers2)); // 6
count(target22, numbers2); // 대상 원소가 3개 존재합니다.
}
}