Binary Search

🎃 개념

1. 이분 탐색이란? (Binray Search)

   • 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘
   • 리스트의 크기를 N이라고 했을 때, O(logN)의 시간이 걸린다.
   • 정수와 달리, 실수에서는 LEFT와 RIGHT의 범위를 MID로 맞춰주어야 한다.
   • 이분 탐색은 다른 유형과 혼합하여 출제되는 경우가 많고, 해당 문제가 이분 탐색인지조차 파악하기 어렵게 출제하는 경우도 있다.
   • 문제
     • BOJ1654 랜선 자르기
     • BOJ1981 배열에서 이동
     • BOJ1561 놀이 공원

2. 상한과 하한이란? (Upper & Lower Bound)

   • 상한 : 큰 수 중 첫 번째 수
   • 하한 : 크거나 같은 수 중 첫 번째 수
   • algorithm::equal_range(it first, it last, value)

3. equal_range

algorithm::equal_range(it first, it last, value)

구간 [first, last)에서 value의 lower_bound와 upper_bound를 pair로 반환
→ 두 반환값의 차의 절댓값이 해당 원소(value)의 개수

4. 삼분 탐색이란? (Ternary Search)
   • 값이 커지다가 작아지거나, 작아지다가 커지는 경우에만 사용 가능한 기법
   • 이분 탐색과 유사하나, 2등분이 아닌 3등분으로 문제를 해결한다.
   • 실수와 달리, 정수의 경우에는 삼분 탐색을 통해 근사 범위만 구해놓고 이후 브루트 포스로 정확한 값을 찾는다.
   • 문제
     • BOJ11664 선분과 점
     • BOJ11662 민호와 강호
     • BOJ8986 전봇대 (정수)

🎃 조건

• 결정 문제의 답이 이분적이어야 한다.
  (결정 문제를 잘 선정하는 것이 중요하다!)
• 순차 접근이 가능하고, 정렬되어 있는 자료구조에서만 사용 가능하다.