이분 탐색

이분 탐색/이진 탐색(Binary Search)

이분 탐색(Binary Search)이란, 정렬된 리스트에서 탐색 범위를 절반씩 줄여가며 값의 위치를 찾아내는 알고리즘이다.

 

필요 조건

• 내부 데이터가 정렬 되어 있어야 한다.
• Random Access가 가능해야 한다. (이분 탐색의 성능상 효율을 보기 위해 필요)

 

특징

• 한번 탐색할 때마다, 탐색 범위가 절반씩 줄어든다.
• 시간 복잡도가 O(logN) 으로 탐색 속도가 빠르다.

 

구현 방법

1. iteration version

int binary_search(int A[], int L, int R, int T)
{
	while (L <= R)
	{
		int M = (L + R) / 2;

		if (T < A[M])
			R = M - 1;
		else if (T > A[M])
			L = M + 1;
		else
			return M;
	}

	return -1; // unsuccessful
}

특징

• 배열 인덱스 범위를 [L, R]과 같은 폐구간(closed interval)으로 표현. ex) L = 0, R = N - 1
• 중복 데이터를 고려하지 않음

 

알고리즘

• 탐색 종료 조건 : L > R (L == R 인 경우에도 탐색한다)
• M = floor( (L + R) / 2 ) => (L + R) / 2
• 탐색
  1. T < A[M] 인 경우 : R = M - 1
  2. T > A[M] 인 경우 : L = M + 1
  3. 그 이외 : return M

 

2. recursion version

int binary_search(int A[], int L, int R, int T)
{
	if (L > R) return -1;

	int M = (L + R) / 2;
	if (T < A[M])
		return binary_search(A, L, M - 1, T);
	else if(A[M] < T)
		return binary_search(A, M + 1, R, T);
	return M;
}

 

3. 비교 구문이 하나 생략한 버전

int binary_search(int A[], int L, int R, int T) // L = 0, R = N - 1
{
	while (L != R) // L < R
	{
		int M = (L + R + 1) / 2; // ceil( (L + R) / 2 ) 

		if (T < A[M])
			R = M - 1;
		else
			L = M;
	}

	if (A[L] == T)
	{
		return L;
	}

	return -1; // unsuccessful
}

반복 구문에서 A[M] == T 비교 구문이 생략되고 마지막에 한번만 검사한다.

 

설명

• 범위 [L, R]
• 탐색 종료 조건 L == R (또는 L >= R)
  • A[L]에 찾고자 하는 값이 있을수도, 없을 수도 있다.
• M = ceil( (L + R) / 2 ) => (L + R + 1) / 2
  • L < M <= R
• T <= A[M] 인 경우, L = M 으로 설정
  
  • A[M] == T 인 경우, 다음 탐색 부터 R값만 계속 줄어든다.
  • T < A[M] 인 경우, 다음 탐색 때 M값에 따라 L값이 증가하거나 R 값이 감소한다.

 

 

4. 조건을 만족하는 값 중 가장 알맞은 값 찾기 (중복 데이터 포함)

1) leftmost element

// leftmost element
int binary_search(int A[], int L, int R, int T) // [L, R)
{
	while (L < R)
	{
		int M = (L + R) / 2;
		if (A[M] < T)
			L = M + 1;
		else
			R = M;
	}

	if (A[L] == T)
	{
		return L;
	}

	return -1;
}

 

2) rightmost element

// rightmost element
int binary_search(int A[], int L, int R, int T) // [L, R)
{
	while (L < R)
	{
		int M = (L + R) / 2;
		if (A[M] > T)
			R = M;
		else
			L = M + 1;
	}

	if (A[R - 1] == T)
	{
		return R - 1;
	}

	return -1;
}

 

위 구현에서는 [L, R)과 같이 반 열린 구간으로 범위를 설정했다. ( L이상 R 미만 )

예를 들어, 인덱스 초기 값을 L = 0, R = N 으로 설정한다.

 

이 방법은 *파라메트릭 서치(parametric search) 문제를 풀 때 유용한 형태이다.

파라메트릭 서치 문제를 이진 탐색으로 풀 수 있는데, 다음과 같은 형태를 띈다.

(1) 조건을 만족하는 값 중 (2) 최소, 최대 값을 구할 때 사용된다.

 

*파라메트릭 서치 : 최적화 문제를 결정 문제로 바꿔서 푸는 문제

*최적화 문제 : 함수값을 최적화(최대화 또는 최소화)시키는 파라미터(변수) 조합을 찾는 문제

*결정 문제 : 예, 아니오로 답하는 문제

 

특징

• 조건을 만족하는지, 예, 아니오로 답할 수 있다
• 조건을 만족하는 값 중 최적화 값(최소, 최대) 값을 구한다.

 

References

en.wikipedia.org/wiki/Binary_search_algorithm

파라매트릭 서치(Parametric Search)

이진 탐색, 이분 탐색(binary search) 구현시 고려할 것들