[알고리즘] 이진탐색, 재귀함수

이진탐색(이분탐색) binary search

업다운 게임

전체범위의 딱 절반으로 탐색

총 배열의 길이가 N이라고 할때 그 절반을 탐색하므로 N/2 그다음 N/2/2 이므로 N/(2^2).... 가면 N/2^k 가 되고 이렇게 무한히 반복하다보면 1개만 남았을때를 가정하면 N/2^k = 1이 여야 하므로 k = log N 이된다. 즉 시간복잡도는 O(log N) 이라고 할수있다.

만약 배열이 정렬이 되어있지않다면 이진탐색이 되지않는다. 이럴때 정렬을 이용하여야한다.

재귀함수

자신의 함수안에서 다시한번 자신의 함수를 호출한다.

예를들어 60에서 0까지 카운트하는 함수를 만들때 위와같이 재귀함수를 쓴다.

팩토리얼

3! = 321

4! = 4321=43!

즉, Factorial(n)=n*Factorial(n-1)

Factorial(n-1)=(n-1)*Factorial(n-2)

... Factorial(1)=1