이진 탐색(Binary Search)은 정렬된 데이터를 탐색하는 알고리즘 중 하나입니다. 데이터를 빠르게 탐색할 수 있어 매우 효율적인 탐색 알고리즘 중 하나로 알려져 있습니다.

개요

이진 탐색은 탐색할 데이터를 **중앙값(middle)**을 기준으로 둘로 분할한 후, 원하는 데이터가 중앙값보다 작으면 중앙값의 왼쪽 부분을, 반대의 경우에는 중앙값의 오른쪽 부분을 선택하여 다시 탐색하는 알고리즘입니다.

• 탐색 대상인 데이터가 정렬된 상태여야 합니다.

동작 방식

1. 정렬된 데이터의 중앙값을 선택합니다.
2. 찾고자 하는 값과 중앙값을 비교합니다.
3. 찾고자 하는 값이 중앙값보다 작으면 중앙값의 왼쪽 부분에서 탐색을 시작합니다.
4. 찾고자 하는 값이 중앙값보다 크면 중앙값의 오른쪽 부분에서 탐색을 시작합니다.
5. 탐색하고자 하는 값이 중앙값과 같은 경우, 검색을 종료합니다.
6. 찾고자 하는 값이 없는 경우, 데이터의 모든 값을 탐색할 때까지 위의 과정을 반복합니다.

시간 복잡도

이진 탐색의 시간 복잡도는 O(log n) 입니다.