BinarySearch 이진 탐색

#include<stdio.h>
#include<stdlib.h>

// recursive
// assume that array is sorted
template <typename T>
T BinarySearch(const T* arr, int left, int right, const T x) {
	if (right >= 1) {
		int mid = (left + right) / 2;

		if (*(arr + mid) == x) return mid;

		if (*(arr + mid) < x) return BinarySearch(arr, mid + 1, right, x);
		else return BinarySearch(arr, left, mid - 1, x);
	}

	return EXIT_FAILURE;
}

 

TC (Time Complexity) 재귀 호출한다고 가정시

D&C = Devide + Conquer + Combine

Combine = 0 Binary search에서는 combine 단계가 없음

Devide = 1

Conquer = T(n/2) >> 나누고 둘 중 하나를 선택하기 때문에

T(n) = 1 + T(n/2)

      = 1 + 1 + T(n/4)

      = 2 + 1 + T(n/8)

      assume n = 2^k

      = T(2^k/2^k) +k   (k == log n)

      = O(log n)