Binary Search

데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다.

데이터의 중앙값과 찾고자 하는 값을 비교해 절반씩 탐색하며 대상을 찾는다.

시간 복잡도는 O(logN)이다.

🔰이분 탐색 과정

오름차순으로 정렬된 데이터가 있다고 가정하자.

1. 현재 데이터셋의 중앙값을 선택한다.
2. 중앙값이 타겟보다 클 때, 중앙값 기준으로 왼쪽 데이터셋을 선택한다. 작을 때는 오른쪽 데이터셋을 선택한다.
3. 위 과정을 반복하다가 중앙값과 타겟 데이터의 값이 같으면 탐색을 종료한다.