이분 탐색(Binary Search), 매개변수 탐색(Parametric Search)

정리가 덜 되었지만 참고용으로 빠르게 출고, 이후 수정 예정

이분 탐색(Binary Search)

개요

탐색기법중 하나로, 배열이 정렬되어 있을 때 사용할 수 있다. 시간복잡도는 $O(logN)$이다.

의사코드

left = 0, right = N; // 1. 범위를 정한다.
while (left <= right) {
  mid = (left + right)  // 2. 중앙 위치를 탐색

  if (target < mid)     // 3. 결정문에 따라 위치를 반환하거나, 범위를 절반으로 조정
    right = mid - 1;
  else if (target > mid)
    left = mid + 1;
  else
    return mid;  // 값을 찾았으면 return, 못 찾았으면 범위를 절반으로 줄임
}

return -1;

STL

해당 알고리즘은 헤더에 구현되어 있다. 시간복잡도는 $O(logN)$

주의점은 배열은 반드시 오름차순으로 정렬되어 있어야 한다. 또한 반환값은 bool형이다.

binary_search(vec.begin(), vec.end(), target);
// target이 있으면 true, 없다면 false를 반환한다.

binary_search

매개변수 탐색(Parametric Search)

개요

이분탐색(Binary Search)와 비슷한 탐색법이다. 둘의 가장 큰 차이점은 다음과 같다.

• 이분탐색은 목표값이 존재하는지, 어느 위치에 있는지 찾는 것을 초점으로 한다.
• 매개변수 탐색은 조건에 가장 근접하는 값을 찾는 것을 초점으로 한다.

// 나중에 추가 예정

upper_bound와 lower_bound

개요

매개변수 탐색에서 응용할 수 있는 알고리즘이다.

배열이 오름차순으로 정렬되어 있다고 가정하여 사용했을 때, 두 알고리즘의 차이점은 다음과 같다.

• upper_bound는 배열에서 목표값을 초과하는 값 중에서 가장 좌측에 위치한 값을 찾는 알고리즘이다.
• lower_bound는 배열에서 목표값과 같거나 큰 값 중에서 가장 좌측에 위치한 값을 찾는 알고리즘이다.

구현

int upper_bound(int target, vector<int> &v) {
  int left = 0, right = v.size() - 1;

  while (left < right) {
    int mid = (left + right) / 2;

    if (target <= v[mid]) {  // 해당 부분이 다르다
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return right;
}

int lower_bound(int target, vector<int> &v {
  int left = 0, right = v.size() - 1;

  while (left < right) {  // 해당 부분이 다르다
    int mid = (left + right) / 2;

    if (target < v[mid]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return right;
}

STL

해당 알고리즘은 헤더에 구현되어 있다. 시간복잡도는 $O(logN)$

사용시 주의점은 매개변수로 사용하는 배열은 반드시 오름차순으로 정렬되어 있어야 한다.

auto lower = lower_bound(vec.begin(), vec.end(), key);
// iterator 형태로 lower에 저장된다.

auto upper = upper_bound(vec.begin(), vec.end(), key);
// iterator 형태로 upper에 저장된다.

lower_bound
upper_bound

예제

• BOJ 1654 - 랜선 자르기 <- 가장 기초적인 문제
• BOJ 1300 - K번째 수 <- 접근법 향상을 위한 문제

그 외 solved.ac 이분 탐색(binary_search) 태그 및 매개 변수 탐색(parametric_search) 태그 문제들..

참조

• [C++ Algorithm] 이분 탐색(Binary Search)
• [C++ Algorithm] 매개 변수 탐색(Parametric Search)