이진 탐색(Binary Search)은 알고리즘의 대표적인 고전 문제입니다. 정렬된 배열에서 원하는 값을 효율적으로 찾을 수 있게 해주는 이 알고리즘은, 검색 범위를 절반씩 줄이면서 빠르게 원하는 값을 찾아냅니다.
보통 이진 탐색은 재귀 함수로도, 반복문으로도 구현할 수 있습니다. 이번 글에서는 반복문을 사용하는, 즉 재귀 없이 구현하는 이진 탐색 방법을 소개하고, 실무적으로 왜 이 방식이 더 선호되는지 함께 살펴보겠습니다.
이진 탐색의 핵심 아이디어
- 정렬된 배열의 **중간값(middle)**을 기준으로 값을 비교합니다.
- 찾고자 하는 값이 중간값보다 작으면 왼쪽 범위만, 크면 오른쪽 범위만 다시 탐색합니다.
- 이를 반복하여 값을 찾거나, 검색할 범위가 사라지면 탐색을 종료합니다.
이 방식은 **시간 복잡도 O(log n)**의 효율적인 탐색을 보장합니다.
반복문을 이용한 이진 탐색 구현 (Go 예제)
package main
import (
"fmt"
)
// 반복문을 이용한 이진 탐색
func BinarySearch(arr []int, target int) int {
low := 0
high := len(arr) - 1
for low <= high {
mid := (low + high) / 2
if arr[mid] == target {
return mid // 값을 찾음
} else if arr[mid] < target {
low = mid + 1 // 오른쪽 탐색
} else {
high = mid - 1 // 왼쪽 탐색
}
}
return -1 // 찾지 못한 경우
}사용 예시
func main() {
sortedArr := []int{2, 4, 6, 8, 10, 12, 14, 16}
target := 10
index := BinarySearch(sortedArr, target)
if index != -1 {
fmt.Printf("값 %d는 인덱스 %d에 있습니다.\n", target, index)
} else {
fmt.Printf("값 %d를 배열에서 찾을 수 없습니다.\n", target)
}
}출력 결과
값 10는 인덱스 4에 있습니다.반복문 방식의 장점
| 항목 | 설명 |
|---|---|
| 공간 효율성 | 재귀 호출 스택이 없어 메모리 절약 (공간 복잡도 O(1)) |
| 실행 성능 | 함수 호출 비용이 없으므로 빠름 |
| 안전성 | 스택 오버플로우 우려 없음 |
실제 서비스 코드나 라이브러리에서는 대부분 반복문 방식으로 이진 탐색을 구현합니다. 이유는 단순합니다. 속도와 안정성 모두 우수하기 때문입니다.
재귀와 반복문 비교
| 항목 | 재귀 함수 | 반복문 |
|---|---|---|
| 가독성 | 간결함, 논리적 구조 | 다소 장황할 수 있음 |
| 메모리 사용 | O(log n) 스택 사용 | O(1) 상수 메모리 |
| 성능 | 약간 느릴 수 있음 | 더 빠름 |
| 실무 적합성 | 학습/이해용에 좋음 | 실무에서 선호됨 |
실무 팁: 범위 체크를 신중히!
이진 탐색에서 흔히 하는 실수 중 하나는 mid 계산에서 overflow가 나는 경우입니다. Go에서는 int가 충분히 크지만, 안전하게 다음과 같이 mid를 구하는 것도 좋은 습관입니다:
mid := low + (high - low) / 2
이 방식은 C, Java 같은 언어에서 overflow를 피하기 위해 널리 사용되는 방식입니다.
마무리
이진 탐색은 빠르고 정확하게 값을 찾을 수 있는 강력한 알고리즘입니다. Go에서는 반복문을 통해 간결하고 효율적으로 구현할 수 있으며, 실제 서비스 코드에서도 널리 사용됩니다. 특히 재귀보다 안정적이고 성능이 좋기 때문에 실무에서는 반복문 방식이 훨씬 더 권장됩니다.
코드의 구조가 단순하고 테스트하기 쉬운 것도 이점입니다. 이 글을 계기로, Go에서 반복문 기반의 알고리즘을 자신 있게 구현해보세요!