이진 탐색(Binary Search)

이진 탐색은 정렬된 데이터에서 원하는 값을 빠르게 찾기 위해 사용되는 대표적인 탐색 알고리즘이다. 업다운 게임을 떠올리면 동작 원리를 쉽게 이해할 수 있다. 숫자가 1부터 100까지 있다고 가정하고, 제한된 횟수 안에 정답을 맞혀야 한다면 가장 먼저 시도해야 할 숫자는 가운데 값인 50이다. 정답이 50보다 크면 51~100 구간만 남고, 반대로 작으면 1~49 구간만 남는다. 이렇게 한 번 시도할 때마다 탐색해야 할 범위가 절반으로 줄어드는 방식이 바로 이진 탐색의 핵심이다.

이 방식이 얼마나 효율적인지는 순차 탐색과 비교해 보면 분명해진다. 순차 탐색은 배열의 앞에서부터 하나씩 순서대로 확인하며 찾는 가장 단순한 방식이다. 예를 들어 1부터 16까지 정렬된 숫자 배열에서 14를 찾는다고 하면, 순차 탐색은 1부터 차례대로 비교해 14에 도달하는 순간에야 탐색이 끝난다. 실제로 이 경우 14번 비교해야 하고, 찾는 값이 마지막에 있다면 16번까지 비교해야 한다. 따라서 순차 탐색의 시간 복잡도는 최악의 경우 O(N)이다.

반면 이진 탐색을 같은 배열에 적용해 보면 탐색 과정이 완전히 다르다. 처음에는 배열의 중앙값인 8을 확인한다. 8은 찾으려는 14보다 작기 때문에 이후 탐색 범위는 9~16으로 좁아진다. 그 다음에는 다시 그 범위의 가운데 값인 12를 확인하고, 다시 탐색 범위를 13~16으로 줄인다. 마지막으로 13번째 인덱스에서 값 14를 확인하면서 탐색이 종료된다. 이 과정에서 필요한 비교 횟수는 단 3번이다. 범위가 절반씩 줄어들기 때문에 배열의 길이가 커질수록 효율성 차이는 더욱 극적으로 벌어진다.

이진 탐색의 시간 복잡도가 O(logN)인 이유도 여기에 있다. 첫 번째 탐색 후 남는 요소는 N/2, 두 번째는 N/4, 세 번째는 N/8이 되고, k번째 탐색 후에는 N/2^k 개가 남는다. 이 값이 1이 되는 시점이 탐색 종료 시점인데, 이를 수식으로 표현하면 N/2^k = 1이 되고, 이를 정리하면 k = log₂N이 된다. 빅오 표기법에서는 밑의 상수는 중요하지 않기 때문에 O(logN)으로 표기한다. 복잡해 보이지만 “탐색 범위가 매번 절반으로 줄어든다”는 점이 중요하다.

이 방식의 장점은 데이터가 많을수록 더 강력하게 드러난다. 예를 들어 100만 개의 정렬된 데이터가 있다고 가정하면, 순차 탐색은 최악의 경우 100만 번 모두 확인해야 한다. 반면 이진 탐색은 log₂1,000,000 ≈ 20 정도의 연산만으로 원하는 값을 찾는다. 100만 vs 20, 이 차이가 얼마나 큰지 단번에 느껴질 것이다. 이런 이유로 정렬된 배열에서의 탐색 문제는 거의 항상 이진 탐색이 기본 전략이 된다.