• 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음

핵심 이론

이진 탐색 과정

1. 현재 데이터셋의 중앙값(median) 선택
2. 중앙값 > 타깃 데이터(target data)일 때 중앙값 기준으로 왼쪽 데이터셋 선택
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋 선택
4. 과정 1.~3.을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료

[029] 원하는 정수 찾기

• https://www.acmicpc.net/problem/1920
• 이진 탐색을 적용하면 O(nlogn) 시간 복잡도로 해결

[030] 블루레이 만들기

• https://www.acmicpc.net/problem/2343
• 가장 긴 강의 ~ 모든 강의들의 합
• 마지막에 start+1해서 최소 블루레이 나옴