[알고리즘] 이분탐색 Binary Search

O(n)이 걸리는 선형 탐색을 O(log n)로 줄일 수 있는 방법이다.

 

일반적으로 이분탐색이라 하면

// 주어진 조건 내에서 최솟값을 구하라고 할 때

int left = 0, right = MAX;
while(left <= right){
  int mid = (left + right)/2;
  if(mid < 주어진 조건){
    right = mid+1;
  }else {
    left = mid;
  }
}

return left;


// 주어진 조건 내에서 최댓값을 구하라고 할 때
int left = 0, right = MAX;
while(left <= right){
  int mid = (left + right)/2;
  if(mid > 주어진 조건){
    left = mid-1;
  }else {
    right = mid;
  }
}

return right;

요런 식으로 식을 세운다.

 

관련문제는:

[백준] 나무자르기

www.acmicpc.net/problem/2805

[백준] 랜선 자르기

www.acmicpc.net/problem/1654

[백준] 공유기 설치

www.acmicpc.net/problem/2110

가 있다.

 

 

이분탐색의 확장: 

c++의 lower_bound와 upper_bound가 있다.

www.cplusplus.com/reference/algorithm/lower_bound/

 

lower_bound는 찾는 값보다 크거나 같은 값이 처음으로 등장하는 iterator를 리턴

upper_bound는 찾는 값보다 큰 값이 처음으로 등장하는 iterator를 리턴한다.

주의할 점은 두 함수 모두 벡터/배열을 정렬 후에 사용해야 한다는 점이다.

두 함수 모두 iterator를 리턴하므로 사용 시에 벡터의 경우 v.begin()을, 배열의 경우 주소값인 arr를 빼면 위치가 나온다.

#include <algorithm>
#include <iostream>
using namespace std;

int main(void){
  vector<int>::iterator low,up;
  
  sort(v.begin(), v.end()); // 정렬 필수
  
  low = lower_bound(v.begin(), v.end(), val);
  // 찾고자 하는 값 val보다 크거나 같은 값이 처음으로 등장하는 iterator를 리턴
  
  up = upper_bound(v.begin(), v.end(), val);
  // 찾고자 하는 값 val보다 큰 값이 처음으로 등장하는 iterator를 리턴
  
  cout<<lower_bound(v.begin(), v.end(), val) - v.begin() + 1 << "\n";
}

 

lower_bound와 upper_bound를 이분탐색을 사용해서 직접 구현할 수 있다.

int lower_bound(int arr[], int len, int n){
  int left = 0, right = arr[len-1];
  while(left<right){
    int mid = (left + right)/2;
    if(arr[mid] >= n) right = mid;
    else left = mid+1;
  }
  return right;
}

int upper_bound(int arr[], int len, int n){
  int left = 0, right = arr[len-1];
  while(left<right){
    int mid = (left + right)/2;
    if(arr[mid] > n) right = mid;
    else left = mid+1;
  }
  return right;
}

 

그렇다면 이게 언제 쓰이느냐..

범위 안에 해당하는 숫자의 개수를 찾는데 유용하다.

www.usaco.org/index.php?page=viewproblem2&cpid=666

 

또는 LIS 계산할때..정말 유용하다.

다음에 자세히 다뤄볼 예정

 

암튼 자주 등장하는 주제이니 꼭 기억하자