이진 탐색 알고리즘의 재귀적 구현
Programming/Data Structure 2012. 12. 23. 18:47 |이진 탐색 알고리즘은 수식적으로 표현하기는 부적절하지만 알고리즘의 논리 자체는 재귀적이기 때문에 충분히 가능하다.
이진 탐색 알고리즘은 두 번째 시도 이후부터는 탐색 대상을 찾을 때까지 동일한 패턴을 반복한다.
때문에 알고리즘 자체는 재귀적인 성격을 지니고 있다. 그래서 재귀적으로 정의가 가능하다.
# 이진 탐색 알고리즘의 반복 패턴
1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인.
2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작.
# 재귀 함수의 탈출 조건
"탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우"
이진 탐색 알고리즘을 성능이 떨어지는 재귀함수 기반으로 구현한 이유.
- 재귀함수에 익숙해지기 위함이다.
- 재귀 함수를 기반으로 구현된 위의 이진 탐색 알고리즘도 자연스럽게 이해할 수 있을 정도가 되어야 한다
'Programming > Data Structure' 카테고리의 다른 글
추상 자료형: Abstract Data Type (0) | 2012.12.24 |
---|---|
하노이 타워 : The Tower of Hanoi (0) | 2012.12.24 |
재귀의 활용 : Fibonacci Sequence (0) | 2012.12.23 |
함수의 재귀적 호출 (0) | 2012.12.23 |
순차 탐색 알고리즘과 이진 탐색 알고리즘의 비교 (0) | 2012.12.23 |