'이진탐색 재귀함수'에 해당되는 글 1건

이진탐색

배열에서 어떤 원소를 찾을때 그 원소가 있는지 어떻게 찾을 수 있을까요?b가장 간단한 방법은 아무래도 for루프를 실행하면서 하나하씩 일치하는지 검색하는 방법이겠죠?

너무 쉽습니다.

int arr[10] = { 3,5,6,8,9,11,14,15,18,20 };
int i;
int data = 18;
int found = -1;
for (i = 0; i < sizeof(arr); i++)
	if (arr[i] == data) found = arr[i];

printf("found:%d\n", found);

이보다 빠르게 찾을 수는 없을까요? 이 탐색시간을 O(logn)으로 수행할 수 있는 방법이 바로 이진탐색(Binary Search)입니다.

개념

이진탐색은 우선 정렬된 배열에서만 사용가능합니다. 정렬되지 않았다면 정렬을 해주어야하지요. 

또한 이진탐색은 3개의 변수가 사용이 됩니다. 바로 left, mid, right이지요. 초기상태에서 배열의 가장 첫번째를 가리키고 있는 left, 배열의 가장 끝을 가리키고 있는 right, left와 right의 중간을 가리키고 있는 변수가 mid입니다.

우리가 찾는 원소를 data라고 합시다. 우리는 mid의 값을 중요하게 생각해야 돼요. mid자리에 있는 원소가 data와 같다면 그 원소를 찾게 된 것이죠.

만약 mid자리에 있는 원소보다 data가 크다면 left~mid까지 범위는 탐색할 필요가 없게 되지요. 반대로 mid자리 원소보다 data가 작다면 mid~right까지의 범위는 탐색할 필요가 없습니다.

찾지 못 한다면 범위를 바꾸어줘야합니다. left~mid까지의 범위를 탐색할 필요가 없다면 이제 left=mid+1이 되고 mid 역시 left, right의 중간값인 (left+right)/2가 됩니다. 그 반대도 역시 마찬가지죠. 정리하자면 이렇습니다.

이제 실제로 어떻게 데이터가 검색되는지 보도록하지요.

배열의 원소 arr = { 3, 5, 6, 8, 9, 11, 14, 15, 18, 20}이라고 칩시다.

다음은 여기서 18을 찾는 과정을 보여줍니다.

우선 초기에 left=0, mid=4, right=9입니다. mid의 값은 (left+right)/2로 계산된 값입니다. arr[mid]와 data를 비교해보니 data가 더 크군요. 그러니까 left와 mid까지의 범위는 볼 필요가 없습니다. 정렬된 배열이기 때문에 18보다 작은 것들은 left~mid까지이니까요.

이제 범위를 옮기도록 하지요. left=mid+1이 되고 mid는 그 중간 값인 (left+right)/2가 됩니다. 이제 다시 arr[mid]와 data를 비교해보니 data가 더 크지요? 다시 범위를 바꿉니다

이제 left와 mid는 같은 값이 되고 다시 arr[mid]와 data를 비교해보니 일치합니다. data가 배열에 있다는 것을 알게 됐습니다.

만일 data를 찾지 못한다면 left와 right는 서로 뒤집히게 됩니다. 그러니까 left가 right보다 더 크게 변한다는 의미입니다.

구현

아래코드는 원소가 존재한다면 몇번째에 위치하는지 인덱스를 구해냅니다. 구현을 통해서 위의 결과를 확인해보세요. 

int binarySearch(int *arr,int size,int data) {
	int left = 0;
	int right = size - 1;
	
	while (left<=right) {
		int mid = (left + right) / 2;
		if (arr[mid] == data)
			return mid;
		if (arr[mid] > data)
			right = mid - 1;
		else
			left = mid + 1;
	}

	return -1;
}

초기 left=0, right=size-1입니다. 가장 처음과 끝을 가리키고 있지요. while루프의 탈출조건은 left가 right보다 같거나 작을때까지 입니다. 

while루프에서는 우선 mid의 값을 구하고 이 mid 원소와 data를 비교하여 같은지 확인합니다. 원소를 찾지 못하면 left와 right의 값을 바꿉니다.

간단하죠?

이진탐색은 재귀함수로도 간단하게 구현이 가능합니다.

int binarySearch(int *arr,int left,int right,int data) {
	if (left > right) return -1;

	int mid = (left + right) / 2;
	
	if (arr[mid] == data) return mid;
	if (arr[mid] > data)
		return binarySearch(arr, left, mid - 1, data);
	return binarySearch(arr, mid + 1, right, data);
}

재귀함수도 너무 간단하죠? 기자사례는 위의 while루프와 같다는 것을 알 수 있습니다. 재귀함수의 종료 조건이되지요.

그 후 내부 코드는 while루프의 내부 코드와 유사하다는 것을 알 수 있습니다. 그렇죠?

아참, 주의할것은 호출할때 binarySearch(arr,0, (sizeof(arr)/sizeof(int))-1, data)로 호출해야합니다. 만약 arr의 크기가 10이라면 9를 right의 매개변수로 전달하는 것이죠. 왜냐면 크기가 10인 배열의 마지막 인덱스는 9이기 때문이죠.

시간복잡도

결국 이진탐색은 반으로 계속 줄여가면서 원소를 탐색하기 때문에 시간복잡도는 O(logn)이라는 사실을 알 수 있습니다. O(n)에 비해서는 훨씬 빠른 속도입니다.

하지만 배열이 정렬된 상태여야 된다는 점이 조금 아쉬운 부분이기는 하지만 하나의 배열에서 검색을 자주하는 상황이라면 한번 정렬만 하면 다음부터는 계속 O(logn)의 속도로 원소를 찾을 수 있죠.