이분탐색

이분탐색

정렬된 배열에서 원하는 값을 O(logn)의 시간복잡도로 찾을 수 있는 알고리즘이다.

배열의 중앙에 있는 값을 조사하여 찾고자 하는 값이 배열의 왼쪽 또는 오른쪽에 있는지를 알아내어 탐색의 범위를 절반으로 줄인다.

이분탐색 구현

반복문을 이용한 이분탐색

int binarySearch(int x, int s, int e) {
	while (s <= e) {
		int m = (s + e) / 2;
		if (x == a[m])
			return m;
		else if (x < a[m])
			e = m - 1;
		else
			s = m + 1;
	}
	return -1;
}

재귀를 이용한 이분탐색

int binarySearch(int x, int s, int e) {
	if (s > e)
		return -1;
	int m = (s + e) / 2;
	if(x == a[m])
		return m;
	else if (x < a[m])
		return binarySearch(x, s, m - 1);
	else
		return binarySearch(x, m + 1, e);
}