데이터를 다루다 보면 특정 키(key)를 찾아야 하는 상황이 자주 발생합니다. 이때 어떤 탐색 기법을 선택하느냐에 따라 프로그램의 성능이 크게 달라질 수 있습니다. 이 글에서는 가장 대표적인 두 가지 탐색 기법인 순차 탐색(Sequential Search)과 이진 탐색(Binary Search)의 핵심적인 차이점을 비교해 살펴보겠습니다.
순차 탐색 vs 이진 탐색 비교표
| 순차 탐색 (Sequential Search) | 이진 탐색 (Binary Search) |
|---|---|
| 시간 복잡도는 O(n) | 시간 복잡도는 O(log n) |
| 첫 번째 위치에 있는 키를 상수 시간(O(1))에 찾을 수 있음 | 중앙 위치에 있는 키를 상수 시간(O(1))에 찾을 수 있음 |
| 컨테이너 내 요소들의 순서가 탐색 결과에 영향을 주지 않음 | 컨테이너 내 요소들이 반드시 정렬되어 있어야 함 |
| 배열과 연결 리스트 모두로 구현 가능 | 연결 리스트에는 직접 구현할 수 없으며, 리스트의 기본 규칙을 변경해야 함 |
| 반복(iterative) 방식으로 동작하는 알고리즘 | 분할 정복(Divide and Conquer) 기법을 사용하는 알고리즘 |
| 구현이 쉽고 필요한 코드량이 적음 | 알고리즘이 다소 복잡하며 더 많은 코드가 필요함 |
| 최악의 경우 N번의 비교가 필요함 | 최악의 경우에도 log n번의 비교면 충분함 |
순차 탐색(Sequential Search)이란?
순차 탐색은 데이터 집합의 처음부터 끝까지 요소를 하나씩 차례대로 확인하며 원하는 키를 찾는 가장 단순한 탐색 방법입니다. 선형 탐색(linear search)이라고도 부르며, 데이터가 정렬되어 있지 않아도 사용할 수 있다는 것이 가장 큰 장점입니다. 대신 최악의 경우 모든 요소를 확인해야 하므로 시간 복잡도는 O(n)입니다.
이진 탐색(Binary Search)이란?
이진 탐색은 정렬된 데이터에서만 사용할 수 있는 고속 탐색 기법입니다. 탐색 범위의 중앙에 있는 값을 기준 값과 비교하여, 찾고자 하는 키가 중앙 값보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 새로운 탐색 범위로 삼습니다. 이 과정이 반복될 때마다 탐색 범위가 절반씩 줄어들기 때문에 시간 복잡도가 O(log n)으로 매우 효율적입니다.
어떤 상황에서 무엇을 사용해야 할까?
데이터 양이 적거나 정렬되어 있지 않은 경우, 또는 연결 리스트처럼 임의 접근(random access)이 어려운 자료구조라면 순차 탐색이 적합합니다. 반면, 데이터가 많고 이미 정렬되어 있다면 이진 탐색이 압도적으로 빠른 성능을 발휘합니다.
예를 들어 100만 개의 데이터를 탐색한다고 가정해 보겠습니다. 순차 탐색은 최악의 경우 100만 번의 비교가 필요하지만, 이진 탐색은 약 20번(log₂1,000,000 ≈ 20)의 비교만으로 원하는 값을 찾을 수 있습니다. 따라서 대용량 데이터를 다루는 시스템에서는 이진 탐색이 필수적인 선택이라 할 수 있습니다.