바이너리검색

바이너리검색1

검색 방법 중에 가장 기본적이며, 단순한 검색 방법은 선형 검색 입니다.

정렬된 값을 가진 배열이 존재한다면, 이 배열의 맨 왼쪽 부터 오른 쪽까지 순차적으로 검색하여 검색 조건에 맞는 값을 찾아 내는 방법이 되겠습니다

​

1. 선형검색

​​다음은 비교를 위한 일반적으로 가장 간단한 선형 검색에 대한 코드 입니다:

int search(int arr[], int n, int x)
{
	int i;

	for (i=0; i<n; i++) 
		if (arr[i] == x)
			return i;

	return -1;
}​

 

선형 검색의 시간 복잡도는 O(n)이 된다. 즉 찾아야 할 항목이 n 개 이면 n번의 시간이 걸린다는 것이죠.

반면에 다음에 살펴 볼 바이너리 검색은 시간 복잡도를 O(logn)으로 줄이는 알고리즘이 되겠습니다.

이 알고리즘의 주요 내용는 한번의 비교마다 반 씩 검색을 줄이는 방법을 취해 준다는 것입니다.

​

바이너리 검색의 알고리즘은 순서는 다음과 같습니다. 음... 알고리즘? 로직? 뭐 어쨋거나...

 

다음 검색 조건 값 x에 대해서,

1) 중간 요소와 x를 비교
2) x와 중간 요소가 같다면, 중간요소를 리턴한다.
3) 중간요소가 x보다 크다면 왼쪽 서브 배열로 가서 비교
4) 중간요소가 x보다 작다면 오른쪽 서브 배열로 가서 비교한다.

 

​

2. 바이너리 검색의 구현 - C

그럼 이 바이너리 검색 구현에 대해서 알아 보겠습니다. 누구나 알고 있는(?) C 언어를 사용 해서 말이죠.

​

2.1. 메인 함수(C)

 

다음의 바이너리 검색 구현이 되었다면, 해당 검색 구현을 실행 해 주는 메인 함수를 먼저 작성 한 것입니다.

바이너리 검색의 구현에는 재귀적 호출에 의한 검색과 반복 순환문을 통한 검색으로 나누어서 살펴 볼 수 있을 것입니다.

int main(int argc, char *argv[])
{

	int arr[] = {2,5,9,13,24,33,40,56,63};
	int x;
	int ret, len;

	x = atoi(argv[1]);
	len = sizeof(arr)/sizeof(arr[0]);
	ret = binsearch_recur(arr, 0, len, x);

	if(ret == -1) printf("value [%d] not found...\n", x);
	else printf("[%d]th value [%d] found...\n", ret, x);

	ret = binsearch_iter(arr, 0, len, x);

	if(ret == -1) printf("value [%d] not found...\n", x);
	else printf("[%d]th value [%d] found...\n", ret, x);


	return 0;

}​

 

 2.2. 재귀적으로 구현한 함수(C) - binsearch_recur

 직관적으로 재귀적 함수를 통해서 바이너리 검색을 구현 해 볼 수 있습니다.

코드는 다음과 같습니다.

int binsearch_recur(int arr[], int s, int e, int val)
{
	int mid;

	mid = s + (e-s)/2;
	//mid = (e+s)/2;

	if(e >= s)
	{
		if(arr[mid] == val) return mid;
		if(arr[mid] > val) return binsearch_recur(arr, s, mid-1, val);
		if(arr[mid] < val) return binsearch_recur(arr, mid+1, e, val);
	}
	return -1;
}

 

2.3. 반복 순환형 구현(C) - binsearch_iter

 다음은 반복문을 통해서 바이너리 검색을 구현 해 볼 수 있습니다.

코드는 다음과 같습니다.

int binsearch_iter(int arr[], int s, int e, int val)
{
	int mid;

	while(e >= s)
	{

		mid = s + (e-s)/2;

		if(arr[mid] == val) return mid;
		else if(arr[mid] < val) s = mid+1;
		else if(arr[mid] > val) e = mid-1;
	}

	return -1;
}

 

3. 바이너리 검색의 구현 - Java

​그럼 자바에서 어떻게 할까 하는 생각에 자바에서 구현을 만드어 보았습니다.

그닥 크게 다를 것은 없다고 생각이 들고, 이것이 알고리즘이라는 것인가? 하는 생각이 갑자기 드네요.

언어를 초월한 생각??

 

3.1. 메인 함수(Java)

메인 함수는 다음과 같습니다. 

public static void main(String args[])
{
	int arr[] = {2,5,9,13,24,33,40,56,63};
	int x;
	int ret, len;

	BinSearch binarySearch = new BinSearch();

	x = Integer.valueOf(args[0]).intValue();
	len = arr.length;


	ret = binarySearch.binsearchRecur(arr, 0, len, x);

	if(ret == -1) System.out.printf("[Recursive][%d]th value [%d] not found...\n", ret, x);
	else System.out.printf("[Recursive][%d]th value [%d] found...\n", ret, x);

	ret = binarySearch.binsearchIter(arr, 0, len, x);


	if(ret == -1) System.out.printf("[Iterative][%d]th value [%d] not found...\n", ret, x);
	else System.out.printf("[Iterative][%d]th value [%d] found...\n", ret, x);

	return;
}

 

 

3.2. 재귀적 구현(Java) - binsearchRecur

private int binsearchRecur(int arrays[], int start, int end, int search)
{
	int mid = start + (end - start)/2;

	if(end >= start)
	{

	if(arrays[mid] == search) return mid;
	if(arrays[mid] > search) return binsearchRecur(arrays, start, mid -1, search);
	if(arrays[mid] < search) return binsearchRecur(arrays, mid + 1, end, search);
	}

	return -1;

}

 

 3.3. 열거형 구현(C) - binsearchIter

private int binsearchIter(int arrays[], int start, int end, int search)
{

	int mid = -1;

	while(end >= start)
	{
	mid = start + (end-start)/2;

	if(arrays[mid] == search) return mid;
	if(arrays[mid] > search) end = mid -1;
	if( arrays[mid] < search) start = mid + 1;
	}

	return -1;
}

 

 

4. 분석 결과

​시간 복잡도:

바이너리 검색의 시간 복잡도는 다음과 같이 쓸수 있다

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

 

Auxiliary Space:

O(1) 열거형 구현의 경우

O(logn) : 재귀형 호출 스택 공간

 

알고리즘 패러다임:

Divide and Conquer

 

이상.

---

1. http://geeksquiz.com/binary-search/