이분 탐색이란?
오름차순으로 정렬되어 있는 배열에서 데이터를 찾을 때, 탐색 범위를 절반씩 줄여가면서 찾아가는 방법
Binary Search
- 검색이 반복될 때마다, 찾고자 하는 값을 찾을 확률이 두배가 되어 속도가 빠름.
- 단, 정렬된 배열에서만 사용할 수 있음.
이분 탐색 알고리즘
- 처음 중간의 값을 임의의 값으로 선택하고, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식.
- 처음 선택한 중간값이 찾고자하는 값보다 크면 그 값은 새로운 최댓값이 됨
- 처음 선택한 중간값이 찾고자하는 값보다 작으면 그 값은 새로운 최솟값이 됨.
- 값을 찾을 때까지 반복.
시간 복잡도
- 탐색 대상을 절반씩 줄여나가기 때문에, 최악의 경우에도 탐색의 횟수가 log2n.
- Time Complexity : O(logn)
자바 코드
public static int binarySearch(int[] array, int target){
int start = 0; // 시작 값
int end = array.length - 1; // 마지막 값
while(start <= end){
int mid = (end + start) / 2; // 중간 값
if(array[mid] == target) {
// 찾고자 하는 값
return mid;
}
else if(array[mid] < target) {
// 찾고자 하는 값보다 작은 경우
start = mid + 1;
}
else {
// 찾고자 하는 값보다 큰 경우
end = mid - 1;
}
}
// 찾고자 하는 값이 없는 경우
return -1;
}문제 예시
프로그래머스 - 입국 심사
- 탐색할 값을 모든 사람이 심사를 받는데 걸리는 시간의 최솟값(mid)으로 하고 이분 탐색.
- 시작값 : 0, 마지막 값 : 가장 오래걸리는 시간 (times 배열의 최댓값 * n명)
- 단, 이분 탐색은 정렬된 배열에서 사용할 수 있으므로 Array.sort로 먼저 정렬
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
long answer = 0;
Arrays.sort(times);
long start = 0; // 시작 값
long end = (long) n * times[times.length-1]; // 마지막 값 (가장 오래 걸리는 시간)
// 이분 탐색
while(start <= end) {
long count = 0; // 총 심사 받는 사람 수
long mid = (start + end) / 2; // 중간값
// 총 심사 받는 사람 수 계산
for(int i = 0; i < times.length; i++) {
count += mid / times[i];
}
// 시간을 더 줄여 걸리는 시간 최소로 만들어야 함.
if(count >= n) {
end = mid - 1;
answer = mid;
}
// 시간을 더 늘려야 함.
else {
start = mid + 1;
}
}
return answer;
}
}처음에 탐색할 값을 시간이 아닌 배열의 인덱스 값으로 잡아서 시간초과가 나왔다. 그러다가 시간으로 탐색할 값을 잡고 count == n인 경우 바로 answer을 리턴하도록 했더니 모든 테스트케이스가 통과가 안됐다. 그 이유가 시간 중에서도 최솟값을 찾아야 되는데 그냥 리턴해버려서 그런 것 같다. 문제를 꼼꼼하게 잘 읽자..
Studying!!