이진 탐색 / 이분 탐색
이진 탐색이란 정렬돼 있는 데이터에서 특정한 값을 찾아내는 알고리즘이다.
-
이진탐색은 이분탐색이라고도 불린다. 이진탐색은 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식으로 동작한다. 주로 배열의 인덱스를 기준으로 배열 내의 값을 탐색하는데 사용되지만, 리스트, 트리 등에서도 사용할 수 있다.
-
❌하지만 모든 리스트, 트리에서 사용할 수 있는 것이 아니라 반드시 원소들이 일정한 순서(예를 들면 오름차순)로 정렬된 구조에서만 사용할 수 있기 때문에 정렬된 리스트나 트리에서 사용이 가능하다.
-
이진탐색의 시간 복잡도는 O(log n)으로, 배열의 크기에 비례하여 실행 시간이 빨라진다.
따라서 대용량 데이터에서 특정 값의 위치를 찾는 데 용이하다.