이진 탐색

이진 탐색은 데이터가 정렬된 상태에서 탐색하는 데 효과적인 알고리즘이다.

대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 길이를 절반씩 잘라가며 탐색한다.
절반씩 잘라가며 탐색하므로 시간 복잡도는 $O(logN)$을 보인다.

이진 탐색은 구현이 간단하고 탐색에서 사용되는 기본적인 알고리즘이라 부분적인 해결 요소로 자주 사용된다.
입력 범위가 커서 $O(N^2)$이나 $O(N\cdot M)$이 시간 초과가 날 것 같다면 이진 탐색을 떠올려도 된다.

이진 탐색의 설명

이진 탐색은 오름차순으로 정렬된 데이터에서 다음 5가지 과정을 반복한다.

내림차순이라면 조건을 반대로 설정하면 된다.

1. 현재 데이터셋의 중앙값을 선택한다.
2. 중앙값 > 찾고자 하는 값이라면 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 찾고자 하는 값이라면 오른쪽 데이터셋을 선택한다.
4. 1 ~ 3번 과정을 반복한다.
5. 중앙값 == 찾고자 하는 값이라면 탐색을 종료한다.

이진 탐색의 예시

예를 들어 다음과 같은 vector가 있다고 하자.
V = {1, 2, 3, 4, 5, 6, 7, 8, 9}

찾고자 하는 값이 8이라고 했을 때의 경우를 살펴보자.

우선 중앙값을 5로 설정하고, 8과 비교한다.

1 2 3 4 5 6 7 8 9
        ↑
        M

8은 5보다 크기 때문에 중앙값을 기준으로 오른쪽 데이터셋을 선택한다.
그리고 오른쪽 데이터셋에서 다시 중앙값을 설정한다.

6 7 8 9
  ↑
  M

8은 7보다 크기 때문에 중앙값을 기준으로 오른쪽 데이터셋을 선택한다.
그리고 오른쪽 데이터셋에서 다시 중앙값을 설정한다.

8 9
↑
M

8을 발견했으므로 탐색을 종료한다.