이진 탐색(binary search)은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
| 기능 | 특징 | 시간 복잡도 |
|---|---|---|
| 타깃 데이터 탐색 | 중앙값 비교를 통한 대상 축소 방식 | O(logN) |
이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.
구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구한다.
이진 탐색의 핵심 이론
이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다.
(내림차순이라면 조건을 반대로 하여 과정을 반복한다.)
이진 탐색 과정
- 현재 데이터셋의 중앙값(median)을 선택한다.
- 중앙값 > 타깃 데이터(target data)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
- 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
- 과정 1~3을 반복하다가 중앙값 == 타겟 데이터일 때 탐색을 종료한다.
총 16개의 데이터가 있는 데이터셋에서 값이 55인 데이터를 찾는 과정을 그림으로 그려보았다.
이렇게 이진 탐색을 사용하면 N개의 데이터에서 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다. 예를 들면 16개의 데이터면 최대 4번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.
다만 이진 탐색은 데이터가 정렬되어 있어야 한다.
- Do it! 알고리즘 코딩테스트 자바 편
