프로그래밍의 본질은 결국 '데이터 저장'과 '데이터 검색'입니다. 그중에서도 검색(Search)은 사용자가 느끼는 서비스 속도에 직결되는 매우 중요한 기능입니다. "데이터를 찾는 게 다 똑같지 않나?"라고 생각할 수 있지만, 어떤 알고리즘을 사용하느냐에 따라 100만 개의 데이터에서 원하는 값을 찾는 데 1시간이 걸릴 수도, 0.001초가 걸릴 수도 있습니다. 오늘은 가장 기본이 되는 두 가지 검색 방법인 선형 탐색(Linear Search)과 이진 탐색(Binary Search)을 비교하고, 왜 개발자들이 '이진 탐색'을 찬양하는지 그 속도의 비밀을 업다운(Up-Down) 게임에 비유해 설명해 드리겠습니다.
1. 선형 탐색 (Linear Search): 무식하지만 확실한 방법
선형 탐색은 이름 그대로 데이터를 선(Line)처럼 처음부터 끝까지 순서대로 하나씩 확인하는 방법입니다. 가장 단순하고 구현하기 쉽지만, 데이터가 많아질수록 비효율적인 방식입니다.
1-1. 동작 원리
상자에 1부터 100까지 적힌 카드가 무작위로 섞여 있다고 가정해 봅시다. 여기서 '77'을 찾으려면 어떻게 해야 할까요? 1. 첫 번째 카드를 집어 확인합니다. (아니네?) 2. 두 번째 카드를 집어 확인합니다. (아니네?) 3. ... 이 과정을 '77'이 나올 때까지 반복합니다. 운이 나쁘면(최악의 경우) 100번째에 찾을 수도 있습니다. 데이터가 N개라면 최대 N번 확인해야 하므로 시간 복잡도는 O(n)입니다.
2. 이진 탐색 (Binary Search): 반으로 쪼개는 스마트함
이진 탐색은 범위를 절반씩 뚝뚝 잘라내며 찾는 방법입니다. 이 방법의 전제 조건은 "데이터가 반드시 정렬(Sorted)되어 있어야 한다"는 것입니다.
2-1. 업다운(Up-Down) 게임의 원리
술자리 게임인 업다운 게임을 생각해 보세요. 친구가 1부터 100 사이의 숫자 중 하나를 골랐고, 여러분이 맞혀야 합니다. - 가장 현명한 첫 번째 질문은 무엇일까요? 바로 "50?"입니다 (중간값). - 친구가 "Up!"이라고 외치면, 1부터 50까지의 숫자는 쳐다볼 필요도 없이 버려집니다. 범위가 순식간에 50~100으로 줄어듭니다. - 다음 질문은 50과 100의 중간인 "75?"입니다. - 친구가 "Down!"이라고 하면, 75~100도 버려집니다. 범위는 50~75가 됩니다.
이처럼 한 번 비교할 때마다 탐색 범위가 1/2로 줄어들기 때문에 속도가 기하급수적으로 빨라집니다. 이를 O(log n)의 시간 복잡도라고 합니다.
3. 100만 개 데이터에서의 속도 비교 (충격적 차이)
선형 탐색(O(n))과 이진 탐색(O(log n))의 차이는 데이터가 많을수록 극명해집니다.
| 데이터 개수 (N) | 선형 탐색 (최악의 횟수) | 이진 탐색 (최악의 횟수) |
|---|---|---|
| 10개 | 10번 | 4번 |
| 1,000개 | 1,000번 | 약 10번 ($2^{10} \approx 1000$) |
| 1,000,000개 (100만) | 1,000,000번 | 약 20번 ($2^{20} \approx 100만$) |
| 40억 개 (전 세계 인구 반) | 40억 번 | 약 32번 |
믿어지시나요? 40억 개의 데이터 중에서 원하는 값을 찾는데, 이진 탐색을 쓰면 단 32번의 질문이면 충분합니다. 이것이 알고리즘을 배워야 하는 이유입니다.
4. 이진 탐색의 치명적 단점
"그럼 무조건 이진 탐색이 좋은 거 아닌가요?"라고 물을 수 있지만, 치명적인 단점이 하나 있습니다. 바로 '정렬'입니다. 이진 탐색을 하려면 데이터가 반드시 순서대로 정렬되어 있어야 합니다. 정렬되어 있지 않은 데이터라면 정렬하는 데 시간이 더 걸리기 때문에(배보다 배꼽이 더 큼), 데이터가 자주 추가/삭제되어 정렬 상태를 유지하기 힘든 경우에는 그냥 선형 탐색을 쓰거나 해시 테이블을 쓰는 것이 낫습니다.
1. 선형 탐색은 처음부터 끝까지 찾는 O(n) 방식으로, 정렬되지 않은 데이터에서 유효합니다.
2. 이진 탐색은 범위를 절반씩 줄이는 O(log n) 방식으로, 대용량 데이터에서 압도적으로 빠릅니다.
3. 이진 탐색을 쓰려면 데이터가 반드시 정렬(Sorted)되어 있어야 한다는 전제 조건이 필요합니다.