<aside> 💡 **이진 탐색(binary search)**은 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
</aside>
이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다. 구현 및 원리가 간단해 많은 코딩 테스트에서 부분 문제로 자주 출제된다.
이진 탐색 과정(오름차순)
중앙값 > 타겟 데이터**일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.중앙값 < 타겟 데이터**일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.중앙값 == 타겟 데이터**일 때 탐색을 종료한다.
이렇게 이진 탐색을 사용하면 N개의 데이터셋에서 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.
이진 탐색은 데이터가 정렬되어 있어야 한다.
이진 탐색의 용도