Searching - Sequential Search, Binary Search

배열에서 원하는 값을 찾는 탐색 방법은 여러가지가 있다.

배열 안의 데이터가 정렬되어 있는지, 아닌지에 따라 많은 시간 차이가 발생하기도 한다.

어떤 탐색 방법들이 있고, 각각의 상황에 어떤 방법이 적합한지 분석해보자.

 

Sequential Search

가장 단순히 생각할 수 있는 방법인 순차 탐색 알고리즘이다.

순차 탐색은 말 그대로 목표한 값을 찾을 때까지 배열 안의 모든 데이터를 순차적으로 비교하는 방법이다.

 

int seqSearch(int* E, int n, int K) {
	int ans = -1;
	for (int i = 0; i<n; i++) {
		if (E[i] == K) {
			ans = i;
			break;
		}
	}
	return ans;
}

해당 알고리즘은 배열 안에 찾고자 하는 값이 없을 경우 모든 entry를 살펴봐야 하므로 O(n)의 복잡도를 갖는다.

 

그렇다면 배열 안의 값이 오름차순으로 정렬되어 있다면 개선할 수 있을지 알아보자.

 

Modified Sequential Search

앞서 말했듯 순차 탐색에서 worst case는 배열 안에 찾고자 하는 값이 존재하지 않는 경우이다.

배열 안의 값이 정렬되어 있다면 해당 값보다 작거나 같은 부분까지만 탐색함으로써 시간을 줄일 수 있다.

 

int seqSearchMod(int* E, int n, int K) {
	int ans = -1;
	for (int i = 0; i<n; i++) {
		if (K > E[i])
			continue;
		if (K < E[i])
			break;
		ans = i;
		break;
	}
	return ans;
}

현재 값이 찾고자 하는 값보다 작으면 다음 값을 보고, 찾고자 하는 값보다 크면 탐색을 중단한다.

이렇게 하면 average case complexity를 O(n/2)까지 줄일 수 있다.

다만 찾고자 하는 값이 배열 안의 모든 값보다 클 경우 여전히 O(n)의 시간이 필요하다.

 

Binary Search

이진 탐색은 정렬된 배열에서 절반씩 탐색 영역을 좁혀가며 탐색하는 방법이다.

배열이 오름차순으로 정렬되어 있다면, 임의의 entry를 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값만 존재한다.

따라서 가운데 값이 찾는 값보다 크면 왼쪽, 작으면 오른쪽 영역으로 탐색 영역을 좁힐 수 있다.

 

 

예를 들어 위와 같은 배열에서 key 값이 6인 entry의 index를 구해보자.

 

 

먼저 첫번째와 마지막 index를 더한 뒤 2로 나누어 가운데 index 값을 구한다. (0+6)÷2 = 3

그 다음 index가 3인 entry의 값과 찾고자 하는 값을 비교한다. 7 > 6

찾고자 하는 값이 더 작기 때문에 가운데 값 7의 왼쪽까지로 구역을 좁혀 다시 반복한다.

 

 

다음 중간값은 2로 찾고자 하는 값 6이 더 크기 때문에 중간값 2의 오른쪽까지로 구역을 좁힌다.

 

 

다음 중간값은 6으로 찾고자 하는 값과 같아, 목표한 entry의 index는 2임을 알 수 있다.

 

이처럼 n개의 entry를 1/2씩 줄여나가면 logn번 후에는 1개로 줄일 수 있다.

원하는 값이 존재하지 않는 worst case에도 logn + 1번의 비교 연산으로 원하는 값이 없음을 알 수 있다.

 

따라서 이진 탐색의 시간복잡도는 O(logn)으로 순차 탐색보다 훨씬 빠른 탐색이 가능하다.

 

※ 일반적으로 로그는 밑이 10일 때 생략하는 것과 달리, 알고리즘 분석에서는 일반적으로 2를 생략하여 표현한다.

 

int binarySearch(int* E, int first, int last, int K) {
	int index;
	if (last < first)
		index = -1;
	else {
		int mid = (first + last) / 2;
		if (K == E[mid])
			index = mid;
		else if (K < E[mid])
			index = binarySearch(E, first, mid - 1, K);
		else
			index = binarySearch(E, mid + 1, last, K);
	}
	return index;
}

코드로는 위와 같이 시작과 끝 index를 조절하며 재귀 함수로 구현할 수 있다.