[알고리즘] 이분탐색

이분탐색

💡 언제 쓸까?

정렬된 배열에서 특정 값을 찾으려고 할 때 빠르게 찾을 수 있다

• 정렬된 배열의 최대 크기가 엄청 큰데 이 중에서 값을 찾으라고 할 때
  • 정렬되지 않았을 경우, sort함수로 먼저 정렬하고 시작
• 시간복잡도 : O(log n)

📢 구현

재귀함수 or 반복문으로 구현 가능하고, 성능 차이도 거의 없다.
하지만 보통 다들 반복문으로 구현하는 듯!

📌 반복문으로 구현

//크기가 size인 arr 배열에서 target 값의 위치 찾기
int search(int *arr, int size, int target){
	int left, right, mid;
	left = 0;
	right = size - 1;
    
    while(left <= right) {
        mid = (left + right) / 2;
        if(arr[mid] > target) {
            right = mid - 1;
        } else if(arr[mid] < target) {
            left = mid + 1;
        } else { //arr[mid] == target
            return mid; //return left, return right도 ok
        }
    }
}

• left == right 일때 최종적으로 목표값을 찾음
• left == right 일때 left == right == mid
  
  

---

📢 lower_bound

target 이상인 값이 처음 나오는 위치(인덱스) 찾기

📌 직접 구현

int lower_bound(int *arr, int target, int size) {
  int left, right, mid;
  left = 0;
  right = size-1;

  while(left<right) { //left<=right 로 하면, l=r=m이고 arr[m]>=target일때 무한반복 걸림
    mid = (left + right) / 2;
    if(arr[mid] >= target) {
      right = mid;
    } else { //arr[mid] < target
      left = mid + 1;
    }
  }
  return left; //return mid; x //return right; o //엥 셋다 되지 않나?
}

📌 라이브러리

#include <algorithm>

//시작~끝에서 target 이상인 값이 처음 나오는 위치를 반환
lower_bound(배열의 시작, 배열의 끝, target);

//사용
int a = lower_bound(arr, arr+6, 3);
int b = lower_bound(v.begin(), v.end(), 2);

• 이진탐색으로 돌아감
• 조건 : 배열/벡터가 오름차순 정렬이어야 함
  
  

---

📢 upper_bound

target 보다 큰 값이 처음 나오는 위치(인덱스) 찾기

📌 직접 구현

int upper_bound(int *arr, int target, int size) {
  int left, right, mid;
  left = 0;
  right = size - 1;

  while(left<right) {
    mid = (left + right) / 2;
    if(arr[mid] <= target) {
      left = mid + 1;
    } else { //arr[mid] > target
      right = mid;
    }
  }
  return left; //return right; o
}

📌 라이브러리

#include <algorithm>

//시작~끝에서 target보다 큰 값이 처음 나오는 위치를 반환
upper_bound(배열의 시작, 배열의 끝, target);

//사용
int a = upeer_bound(arr, arr+6, 3);
int b = upper_bound(v.begin(), v.end(), 2);

📌 사용

• 중복을 포함한 여러 수들의 배열에서, 특정 수의 개수가 몇 개인지 구할 때
• 중복을 포함한 여러 수들의 배열에서, 특정 범위에 속하는 수가 몇 개인지 구할 때
  
  

---

📢 파라메트릭 서치

이분탐색을 이용하여, 최적화 문제를 결정 문제로 바꾸어 해결

• 최적화 문제 : 특정 조건을 만족하는 가장 이상적인 해를 구하기
  • 이 조건을 만족하는 x의 최소값 구하기
• 결정 문제 : 참/거짓으로 결정할 수 있는 문제
  • x가 7일 때, 이 조건을 만족하는가?

📌 예제

3개의 기계에 8개의 작업을 적절히 분배하여
모든 작업을 최대한 빠르게 끝내고자 한다.
그런데, 각 기계들이 하나의 작업을 처리하는 시간이 다른데,
첫번째 기계는 한 개의 작업을 처리하는데 2시간이 걸리고,
두번째 기계는 3시간, 세번째 기계는 7시간이 걸린다.
그렇다면, 모든 작업을 완료하는데 드는 시간의 최솟값은?

1. 모든 작업을 완료하는데 드는 시간이 x라 할 때,
   각 기계가 x시간만에 완료하는 작업 수 = x/2, x/3, x/7
   세 기계가 x시간동안 완료하는 작업 수 = x/2 + x/3 + x/7
   x/2 + x/3 + x/7 >= 8 을 만족하는 최소 x를 구하면 된다.

2. 모든 작업을 완료하는데 드는 시간을 오름차순 배열로 둔게
   arr = {7, 8, 9, 10, 11, 12, 13, 14, 15} 라 하면
   7 = left, 15 = right로 둬서 arr[mid] 값이 저 조건을 만족하는지 체크!
   true(조건 만족) 면, right = mid
   false(조건 불만족) 면, left = mid + 1
right = left = mid 일 때 이분 탐색이 중단되고 x = 9

---

💡 참고 문제

3020 개똥벌레 : lower_bound
2470 두 용액 : 단순히 배열에서 하나의 값을 찾는게 아닌, left와 right의 적당한 합을 조건으로 left, right를 찾아나감(left, right가 답이 됨)