이분탐색 (Binary Search)
- 전체 범위를 이분할하여 가운데의 값을 비교하여 두 영역 중 다른 영역으로 이동하여 탐색
- 시간복잡도 : O(logN)
- 탐색 전 리스트가 반드시 정렬되어 있어야함 -> 배열을 적게 탐색하는 경우 이분탐색 쓰지 않는 것이 나을수도 있음
순차 탐색 vs 이분 탐색
정렬이 안되어있다면 상황에 따라 순차탐색이 더 나을 수도 있다
java
public class BinarySearch {
static int[] arr = {1, 3, 5, 7, 8, 10, 20, 35, 99, 100};
public static void main(String[] args) {
System.out.println("1. 순환 호출을 이용한 이진 탐색");
System.out.println(binarySearch1(5, 0, arr.length-1)); // 2
System.out.println("\n2. 반복을 이용한 이진 탐색");
System.out.println(binarySearch2(20, 0, arr.length-1)); // 6
}
// 재귀적 탐색
static int binarySearch1(int key, int low, int high) {
int mid;
if(low <= high) {
mid = (low + high) / 2;
if(key == arr[mid]) { // 탐색 성공
return mid;
} else if(key < arr[mid]) {
return binarySearch1(key ,low, mid-1); // 왼쪽 부분 탐색
} else {
return binarySearch1(key, mid+1, high); // 오른쪽 부분 탐색
}
}
return -1; // 탐색 실패
}
// 반복적 탐색
static int binarySearch2(int key, int low, int high) {
int mid;
while(low <= high) {
mid = (low + high) / 2;
if(key == arr[mid]) {
return mid;
} else if(key < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1; // 탐색 실패
}
}
c++
bool binary_search(vector<int>& arr, int len, int target){
int low = 0, high = len - 1;
while(low <= high){
int mid = (low + high) / 2;
//원하는 값을 찾았다면 true 반환
if(target == arr[mid]) return true;
// 원하는 값이 더 작다면 검사 범위를 더 낮게 잡아야 한다.
if(target < arr[mid]){
high = mid - 1;
}
// 원하는 값이 더 크다면 검사 범위를 더 크게 잡아야 한다.
else if(target > arr[mid]){
low = mid + 1;
}
}
return false; // 마지막까지 못찾는다면 false 반환
}
Parametric Search
- 이분탐색을 활용하되, 정확한 값이 아닌 가장 근사한 값 찾는 기법
- 방정식 f(x)가 있다면, 값에 최대한 근사한 해를 찾는 기법
- 즉, 찾는 값 자체를 비교하는 것이 아닌 값을 식에 대입하여 나온 결과물 비교해야함
- 최적으로 구할 해를 이분탐색으로 찾는 것
언제 사용하는게 좋을까?
구해야 할 값의 범위가 매우 크다면( 즉, 완전탐색 계산이 불가능) 고려
public static long binarySearch(int need){
long s = 0;
long e = 2_000_000_000;
long returnHeight = 0;
while(s <= e){
long mid = (s + e) / 2;
// 기준값 설정
// 자른 값들의 총합을 이용
long sum = 0;
for(int i = 0; i<arr.length; i++){
int ele = arr[i];
if(ele > mid)
sum += ele - mid;
}
if(sum >= need) { // 조건을 만족하므로 범위를 더 엄밀하게 줄임
s = mid + 1;
returnHeight = mid; // 조건을 충족한다면 일단 저장
}else if(sum < need)
e = mid - 1;
}
return returnHeight;
}
참고 - https://github.com/VSFe/Algorithm_Study?tab=readme-ov-file
'algorithm > 정리' 카테고리의 다른 글
DP (다이나믹 프로그래밍) (0) | 2024.04.08 |
---|---|
이분탐색 추가 - Upper Bound(상한), Lower Bound(하한) (0) | 2024.04.08 |
99클럽 코테 스터디 5일차 TIL - 자바 map 관련 함수 (getOrDefault, equals) (1) | 2024.04.05 |
정렬 알고리즘 (거품, 선택, 삽입, 퀵, 병합, 힙, 계수 정렬) (0) | 2024.04.04 |
Backtracking (0) | 2024.04.03 |