Java 코드
private int binarySearch(int[] arr, int target){
//이진 탐색을 이용해 정렬된 배열 arr안에서 target 인덱스 반환
//target이 없다면 -1을 반환
}
arr배열 안에 있는 인덱스를 찾는 과정이므로, arr의 범위인 [0,arr.length)가 탐색 범위입니다. 찾는 범위는 다음과 같이 각각의 변수로 선언합니다.
int start = 0;
int end = arr.length;
end-start가 양수일 때까지 탐색을 계속 반복해야 합니다.
while(end>start){
}
범위의 중간 인덱스와 그 값을 구합니다.
int mid = (start+end)/2;
int value = arr[mid];
찾아낸 중간값으로 target과의 대소 판단 후 범위를 조정합니다.
if(value==target){
return mid;
}else if(value> target){
//다운
//정답은 더 작은 범위에 있다.
//[start, mid)
end = mid;
}else{
//업
//정답은 더 큰 범위에 있다.
// [mid+1, end)
start = mid+1;
}
private static int binarySearch(int[] arr, int target){
int start = 0;
int end = arr.length;
while(end>start){
int mid = (start+end)/2;
int value = arr[mid];
if(value==mid){
return mid;
}else if(value>target){
end = mid;
}else{
start = mid+1;
}
}
}
정렬기준이 중요한 이유
이진 탐색 문제 대부분은 큰 범위의 정답 후보 중 문제 조건에 맞는 정답을 찾아내는 케이스입니다. 문제에서 요구하는 조건의 검색 결과가 정답 후보의 값에 따라 정렬된 상태인지 확인해야합니다.
이진 탐색은 정확한 값 뿐만 아니라 정답 조건을 만족하는 값 중 가장 큰 값 혹은 가장 작은 값을 찾는데도 많이 사용됩니다. 파라메트릭 서치를 구현하기 위해서는 다음 2가지를 고려해야합니다.
1. 범위 좁히기
2. 범위 표기법
정답 조건을 만족하는 값 중 가장 큰 값을 구하는 경우
중간값을 검사 했을 때 정답을 만족하더라도 더 큰값이 있는지 찾아야합니다. 범위를 큰 쪽으로 좁히되, 검사한 중간 값을 포함해서 좁혀야합니다.
정답 조건을 만족하는 값 중 가장 작은 값을 구하는 경우
중간값을 검사했을 때 정답을 만족하더라도 더 작은 값이 있는지 찾아야합니다. 범위를 작은 쪽으로 좁히되, 검사한 중간값을 포함해서 좁혀야합니다. 이 경우 범위에 2개의 값이 남아있을 때 중간값은 start를 선택합니다. start가 정답 조건을 만족한다면 중간값을 포함한 [start, start] 를 선택하게 됩니다.
반대로 start가 정답 조건을 만족하지 않는다면 큰 값이 들어 있는 범위인 [start+1, end]
하나의 값만 남았다고 해서 무조건 정답이 아니다.
원소가 하나 남았다면 이 값이 정답을 만족하는지 여부를 한 번 더 검사해야합니다.
| 목표 | 범위 표기법 | 구현법 |
|---|---|---|
| 조건 만족하는 가장 큰 값 | [start, end) | |
| 조건 만족하는 가장 작은 값 | [start, end] | |
자바에서는 배열과 리스트에 적용할 수 있는 두 가지 메서드를 제공합니다. 주의해야할 점은 탐색 대상은 항상 정렬되어 있는 상태이어야합니다.
| 자료구조 | 메서드 |
|---|---|
| 배열 | Arrays.binarySearch() |
| 리스트 | Collections.binarySearch() |
앞의 두 메서드는 배열이나 리스트에서 검색하려는 원소가 있다면 해당 원소의 인덱스를 반환합니다. 만약 찾고자 하는 값이 없다면 음수를 반환합니다.
원소가 들어갈 위치 찾기
찾고자 하는 값이 없을 경우 음수 값을 반환합니다. 이 값을 양수로 변환하고 1을 빼면 해당 원소가 들어갈 위치가 됩니다.
import java.util.Arrays;
import java.util.Collections;
public class LDSBinarySearch {
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("Length of LDS: " + lengthOfLDS(nums));
}
public static int lengthOfLDS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// dp 배열 초기화
Integer[] dp = new Integer[nums.length];
int length = 0;
for (int num : nums) {
// 이분 탐색을 통해 현재 num이 들어갈 위치를 찾음
int i = Arrays.binarySearch(dp, 0, length, num, Collections.reverseOrder());
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == length) {
length++;
}
}
return length;
}
}
import java.util.Arrays;
public class LISBinarySearch {
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("Length of LIS: " + lengthOfLIS(nums));
}
public static int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
int length = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, length, num);
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == length) {
length++;
}
}
return length;
}
}