탐색(Search)
선형 탐색 알고리즘(Linear Search)
- 앞에서부터 차례대로 탐색
- 데이터가 정렬되어 있지 않을 경우 사용
- 데이터가 많을수록 비효율적
- O(n)
이진 탐색 알고리즘(Binary Search)
- 정렬 후 중간값을 기준으로 필요없는 부분을 잘라내가며 탐색
- 한번 탐색할때마다 대상이 절반(1/2)으로 줄어듬
- 데이터가 많을수록 효율적
- O(log n)
- 결정 문제에 사용 된다 -> 정답의 범위가 주어지고 이진탐색으로 좁혀나가 최적의 해를 구한다 (파라매트릭 서치)
- 결정 문제 : YES or NO 로 답할 수 있는 문제 -> mid값이 최적의 해인가? YES
방법
- 이분 탐색할 리스트를 정렬한다.
- 이분 탐색 범위의 시작(left)와 끝(right)를 초기화 한다.
- 초기 값을 잘못 설정하면 오답을 유발한다
- mid 값을 도출해 이분 탐색 진행
- 결과에 따라
left=mid+1
orright=mid-1
해서 다음회전 진행
- 닫힌 범위 [0, n]
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
- 열린 범위 (0, n) (★★중요★★)
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return -1;
}
문제유형
1. 배열에 target이 있는 경우 (가장 basic 유형, 위 코드 확인)
2. 배열에 중복된 요소가 있는 경우
(1) 좌측 탐색 (가장 좌측값을 찾는 탐색, leftmost)
// [5,7,7,8,8,10], target = 8
// answer = 3
private int bisectLeft(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) { // ★ 타겟일 경우 범위에 포함
right = mid;
} else {
left = mid + 1;
}
}
return left < nums.length && nums[left] == target ? left : -1;
}
(2) 우측 탐색 (가장 우측값을 찾는 탐색, rightmost)
// [5,7,7,8,8,10], target = 8
// answer = 4
private int bisectRight(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else { // ★ 타겟일 경우 범위에 포함하지 않음
left = mid + 1;
}
}
return 0 < left && nums[left-1] == target ? left-1 : -1;
}
(3) 결정 문제 (파라매드릭 서치)
- 문제에서 주어진 값의 범위를 한정 짓고(left/right) 해당 숫자(mid)가 답에 T/F인지 판단
- 문제의 조건을 수정하여 가상의 FFFFFTTTTT 배열을 구상 할 수 있음
- ex) FFFFFTTTTT 에서 가장 왼쪽의 T를 찾는 문제(=좌측 탐색)
public int smallestDivisor(int[] nums, int threshold) {
// binary search (parametric search)
int left = 1;
int right = 0;
for (int n : nums) {
right = Math.max(n, right);
}
while (left < right) {
int mid = left + (right - left) / 2;
if (condition(mid, nums, threshold)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean condition(int divisor, int[] nums, int threshold) {
int sum = 0;
for (int num : nums) {
sum += (num + divisor - 1) / divisor;
}
return sum <= threshold;
}