[Algorithm] 이분 탐색 (Binary Search)

이분 탐색이란?

이분 탐색은 정렬된 데이터에서 원하는 값을 효율적으로 찾기 위한 검색 알고리즘입니다.

특정 데이터를 찾을 때 O(log n)의 시간 복잡도를 가지므로 빠른 속도로 찾을 수 있습니다.

이분 탐색 작동 원리

1. 데이터의 중간 값과 특정 데이터와 값을 비교한다
2. 중간 값이 특정 데이터 값과 일치하면 종료한다
3. 중간 값이 특정 데이터 값보다 크면, 왼쪽부터 다시 이분 탐색을 한다
4. 중간 값이 특정 데이터 값보다 작으면, 오른쪽부터 다시 이분 탐색을 한다

이분 탐색 활용

검색

정렬된 데이터에서 특정 값을 찾을 때 이분 탐색을 사용합니다.

최적화

최적화 문제에서 이분 탐색을 이용해 가능한 경우의 수를 줄일 수 있습니다.