이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘입니다. 검색 범위를 절반씩 줄이기 때문에 시간 복잡도는 O(log n)으로 매우 효율적입니다.
보통 이진 탐색은 반복문(loop)으로 구현하지만, Go에서는 재귀 함수(Recursive Function)를 통해 더 깔끔하고 직관적인 방식으로 구현할 수도 있습니다.
이번 글에서는 Go 언어를 사용해 재귀 방식으로 Binary Search를 구현하는 방법을 자세히 살펴보겠습니다.
이진 탐색이란?
이진 탐색은 다음 조건에서 사용됩니다:
- 배열이 오름차순(또는 내림차순)으로 정렬되어 있을 것
- 인덱스를 기준으로 중간 값을 선택하고, 찾고자 하는 값과 비교
- 크기를 기준으로 왼쪽 절반 또는 오른쪽 절반만 계속 탐색
예를 들어, [1, 3, 5, 7, 9, 11] 에서 7을 찾는다면:
- 중간값
5<7→ 오른쪽으로 이동 - 다음 중간값
9>7→ 왼쪽으로 이동 - 다음 중간값
7→ 찾음!
Go로 구현한 재귀 이진 탐색 함수
package main
import (
"fmt"
)
// 재귀 이진 탐색 함수
func binarySearch(arr []int, target int, low int, high int) int {
if low > high {
return -1 // 못 찾은 경우
}
mid := (low + high) / 2
if arr[mid] == target {
return mid
} else if arr[mid] > target {
return binarySearch(arr, target, low, mid-1)
} else {
return binarySearch(arr, target, mid+1, high)
}
}사용 예시
func main() {
sortedArr := []int{1, 3, 5, 7, 9, 11, 13}
target := 7
result := binarySearch(sortedArr, target, 0, len(sortedArr)-1)
if result != -1 {
fmt.Printf("값 %d는 인덱스 %d에 있습니다.\n", target, result)
} else {
fmt.Printf("값 %d를 배열에서 찾을 수 없습니다.\n", target)
}
}출력 결과
값 7는 인덱스 3에 있습니다.시간 복잡도
- 최악의 경우 (O(log n)): 배열의 크기를 절반씩 줄이기 때문에, log₂(n) 만큼만 비교하면 됨
- 공간 복잡도 (재귀 호출): O(log n)만큼 스택이 사용됨 (반복문은 O(1) 공간 사용)
Go다운 방식으로 구현 팁
Go에서는 불필요한 전역 변수를 피하고, 함수를 명확하게 분리하는 것이 좋습니다. 그래서 다음처럼 wrapper 함수를 만들어 더 깔끔하게 사용할 수 있습니다:
func BinarySearch(arr []int, target int) int {
return binarySearch(arr, target, 0, len(arr)-1)
}사용자는 내부 인덱스를 몰라도 간단하게 사용할 수 있습니다:
result := BinarySearch([]int{1, 3, 5, 7, 9}, 5)반복문 vs 재귀문: 어느 쪽이 좋을까?
| 방식 | 장점 | 단점 |
|---|---|---|
| 반복문 | 공간 효율성 (O(1)), 빠름 | 코드가 다소 장황할 수 있음 |
| 재귀 함수 | 코드 간결성, 직관적인 구조 | 큰 배열에서는 스택 오버플로우 위험 |
실무에서는 반복문이 더 자주 사용되지만, 알고리즘 공부나 간결한 코드 구현에는 재귀도 훌륭한 선택입니다.
마무리
이진 탐색은 알고리즘 학습자라면 반드시 익혀야 할 기초 중의 기초입니다. Go 언어의 재귀 함수를 활용하면, 이진 탐색 로직을 더 직관적이고 명확하게 표현할 수 있습니다.
처음엔 간단한 배열부터 시작해서, 점차 구조체 정렬이나 사용자 정의 타입으로 확장해보세요. 그렇게 한 발씩 나아가는 것이 Go 언어 실력을 쌓는 가장 좋은 방법입니다.