이진탐색 (binary search) (1) 재귀적 구현

이진탐색은 처음부터 끝까지 한개씩 확인하면서 찾는 선형탐색의 시간복잡도 보다 훨씬 빠른 의 시간복잡도를 가지고 있는

함수다. 하지만 이진탐색의 시간복잡도가 의 성능을 가지려면 전제조건이 필요한데, 배열이 정렬 되어있어야 한다.

이진탐색은 정렬되있는 배열에서 중간값을 확인하여 중간값보다 작으면 작은쪽을, 크면 큰쪽에서 다시 이진탐색을 수행하는 탐색이다.

이진탐색의 재귀적과 비재귀적 두가지 방법으로 구현할 수 있는데, 여기에선 재귀적으로 구현을 해볼것이다. 

이미지 출처 : https://anster.tistory.com/152

위의 사진에서 만약에 내가 찾는 숫자가 76이라고 가정해보자.

1. 처음에 중간값 47을 찾고 47은 내가 찾는 76보다 작기 때문에 오른쪽에서 다시 이진탐색을 한다.

47보다 작은 쪽은 내가 찾는 숫자가 보나마나 없기 때문에 볼필요가 없다.

2. 남은 오른쪽에서 중간값인 77을 찾고, 77은 내가 찾는 76보다 크기 때문에 왼쪽에서 다시 이진탐색을 수행한다.

3. 남은 왼쪽의 중간값인 64는 내가 찾는 76보다 작고, 다시 오른쪽에서 이진탐색을 한다.

4. 남은 오른쪽에서 중간값은 한개밖에 안남았고, 그 값이 76이므로 내가 찾는 76과 일치하기 때문에 드디어 찾게 된다.

만약에 남은값이 내가 찾는 값이랑 달랐을 경우에는 배열에 내가 찾는 숫자가 없는 것이다.

이렇게 이진탐색을 예를 들어 확인해 보았고 코드를 보자.

이번에는 재귀함수로 이진탐색을 구현하기 때문에 역시 기저 조건을 생각해 봐야한다. start값이 end값보다 크면 입력이 잘못 들어온

것이기 때문에 주어진 value를 찾을 수 없다는 -1을 리턴하고, 만약에 start와 end가 같다면 arr[start]에 있는 값이 value와 같은지 비교하여

같으면 그자리의 인덱스인 start를 리턴하고 아니라면 없다는 의미에서 -1를 리턴한다. 여기에서 start와 end가 같기 때문에 start를 리턴해도

되고 end를 리턴해도 되지만 나는 start를 리턴하였다.

그리고나서 중간값 찾아 그자리의 숫자가 찾는 값이면 그자리의 인덱스인 mid를 반환하고,

만약 arr[mid]가 찾는 value보다 크다면 찾는 숫자는 arr[mid]에 왼쪽에 있는 것이기 때문에 start부터 mid값 바로왼쪽인 mid-1에서 이진탐색

을 한다. 하지만 arr[mid]가 찾는 value보다 작다면 찾는 숫자는 arr[mid]에 오른쪽에 있는 것이기 때문에 mid값 바로 오른쪽인 mid+1에서

end까지 이진탐색을 수행한다.

이렇게 이진탐색을 재귀적으로 구현할 수 있다.