'이진 탐색 알고리즘의 재귀적 구현'에 해당되는 글 1건

  1. 2012.12.23 이진 탐색 알고리즘의 재귀적 구현

이진 탐색 알고리즘은 수식적으로 표현하기는 부적절하지만 알고리즘의 논리 자체는 재귀적이기 때문에 충분히 가능하다.


이진 탐색 알고리즘은 두 번째 시도 이후부터는 탐색 대상을 찾을 때까지 동일한 패턴을 반복한다. 

때문에 알고리즘 자체는 재귀적인 성격을 지니고 있다. 그래서 재귀적으로 정의가 가능하다. 


# 이진 탐색 알고리즘의 반복 패턴

1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인.

2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작.


# 재귀 함수의 탈출 조건

"탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우"



이진 탐색 알고리즘을 성능이 떨어지는 재귀함수 기반으로 구현한 이유.

- 재귀함수에 익숙해지기 위함이다.

- 재귀 함수를 기반으로 구현된 위의 이진 탐색 알고리즘도 자연스럽게 이해할 수 있을 정도가 되어야 한다


Posted by scii
: