알고리즘이란 어떤 문제를 해결하기 위해 정해진 절차나 규칙을 순서대로 나열한 것입니다. 쉽게 말하면 "이런 상황에서는 이렇게 처리한다"는 문제 풀이 방식이라고 볼 수 있습니다. 오늘은 그 중에서도 탐색 알고리즘인 이분 탐색을 알아보겠습니다.
이분 탐색이란?
이분 탐색(Binary Search)은 정렬된 배열에서 중간값을 기준으로 탐색 범위를 두 부분으로 나누고, 찾는 값이 중간값보다 크면 오른쪽, 작으면 왼쪽만 남겨서 범위를 절반씩 줄여나가는 탐색 방식입니다.
핵심 조건과 개념
① 필수 조건 ㅡ 배열이 정렬되어 있어야 합니다
이분 탐색은 중간값을 보고 "왼쪽에 있을까, 오른쪽에 있을까"를 판단합니다.
배열이 정렬되어 있지 않으면 이 판단 자체가 불가능합니다.
② 세 개의 포인터 ㅡ left, right, mid
탐색 범위의 왼쪽 끝(left), 오른쪽 끝(right), 중간(mid) 세 개의 위치를 기억하면서 움직입니다.
mid = (left + right) // 2 로 계산합니다.
③ 반복 규칙 ㅡ 범위를 절반씩 줄입니다
mid의 값이 찾는 값보다 작으면 left를 mid+1로 올려서 오른쪽만 탐색합니다.
mid의 값이 찾는 값보다 크면 right를 mid-1로 내려서 왼쪽만 탐색합니다.
그래서 왜 이분 탐색을 배우는건지?
1부터 100까지 숫자 중 상대방이 생각한 숫자를 맞히는 Up-Down 게임을 떠올려 봅시다.
방법이 두 가지 있습니다. 첫 번째는 1, 2, 3, 4... 순서대로 하나씩 물어보는 것이고, 두 번째는 "50보다 크나요?"부터 시작해서 범위를 절반씩 줄여나는 것입니다.
첫 번째 방법은 최악의 경우 100번 물어봐야 하지만, 두 번째 방법은 7번 안에 찾을 수 있습니다. 이 두 번째 방법이 바로 이분 탐색의 핵심 아이디어입니다. 데이터가 많아질수록, 하나씩 순서대로 확인하는 방식은 너무 느려지기 때문에 이분 탐색이 필요합니다.
"정렬하는 데도 시간이 걸리지 않나요?"
맞습니다. 정렬 자체도 시간이 걸립니다. 그래서 이분 탐색은 이미 정렬된 데이터가 있거나, 한 번 정렬해두고 탐색을 반복적으로 여러 번 해야 하는 상황에서 진가를 발휘합니다. 정렬 비용보다 탐색 이득이 훨씬 클 때 유리합니다.
실습 ㅡ 동작 과정 따라가기
배열 [3, 7, 12, 18, 25, 31, 40]에서 숫자 25을 찾는 과정을 단계별로 보겠습니다. 처음에는 left=0, right=6으로 시작합니다.
1단계: left=0, right=6, mid=3
arr[3] = 18 < 25 → left를 4로 올립니다 (오른쪽만 탐색)
2단계: left=4, right=6, mid=5
arr[5] = 31 > 25 → right를 4로 내립니다 (왼쪽만 탐색)
3단계: left = 4, right=4, mid=4
arr[4] = 25 → 탐색 완료
코드로 보기
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2); // 중간 인덱스 계산
if (arr[mid] === target) {
return mid; // 찾으면 인덱스 반환
} else if (arr[mid] < target) {
left = mid + 1; // 중간값이 더 작음 → 오른쪽만 탐색
} else {
right = mid - 1; // 중간값이 더 큼 → 왼쪽만 탐색
}
}
return -1; // 없으면 -1 반환
}
const arr = [3, 7, 12, 18, 25, 31, 40];
console.log(binarySearch(arr, 25)); // 출력: 4 (인덱스)
참고 ㅡ for문(선형 탐색)과 비교하면
이분 탐색을 처음 보면 "그냥 for문으로 하나씩 찾으면 되는 거 아닌가?"라는 생각이 자연스럽게 드는데요, 실제로 데이터가 적거나 정렬되지 않은 경우엔 for문이 더 간단하고 적합합니다. 이분 탐색은 정렬된 대용량 데이터를 반복적으로 탐색해야 할 때 차이가 극명하게 드러납니다.
| 항목 | for문 (선형 탐색) | 이분 탐색 |
| 정렬 필요 여부 | 필요 없음 | 반드시 필요 |
| 시간 복잡도 | O(n) | O(log n) |
| 100만 개 탐색 시 | 최대 1,000,000번 | 최대 20번 |
| 언제 쓰는지? | 데이터가 적거나 정렬 안 된 경우 | 데이터가 많고 정렬된 경우 |
시간 복잡도란?
데이터 개수(n)가 늘어날수록 연산 횟수가 얼마나 늘어나는지를 나타내는 지표입니다. O(n)은 데이터가 2배 늘면 연산도 2배, O(log n)은 데이터가 2배 늘어도 연산은 1번만 늘어납니다. 그래서 데이터가 많을수록 둘의 차이가 커집니다.
마치며
이분 탐색의 개념을 배우고 나면 단순히 "정렬된 배열에서 빠르게 찾는 방법 하나"를 익히는 데서 그치지 않습니다. 이분 탐색의 핵심인 "범위를 좁혀가며 판단한다"는 사고방식은 다양한 상황에 응용할 수 있습니다.
예를 들어 특정 조건을 만족하는 최솟값/최댓값을 찾는 문제, 정답이 될 수 있는 범위를 추려가며 문제 등 이분 탐색의 원리를 그대로 가져올 수 있는 경우 많습니다. for문으로도 풀 수 있지만 시간이 오래 걸리는 문제에서, "이 상황이 이분 탐색을 쓸 수 있는 구조인가?"를 판단할 수 있게 되는 것이 진짜 목표입니다.
이것으로 이분 탐색이 무엇인지, 왜 쓰는지, 어떻게 동작하는지까지 살펴보았습니다.궁금한 점은 댓글 남겨주세요!