[알고리즘] binary search, 이진탐색

binary serach, 이진탐색에 대해서 설명하고자 한다. 

이름에서 나타나듯이 중간값이 찾고자 하는 값보다 큰지 작은지 따져가면서 찾아가는 탐색 알고리즘이다.

binary search를 사용하려면, 오름차순으로 정렬되어 input이 들어올 때 가능하다.

 

혹시나 up down 게임을 안다면 이해하기 쉬울 것이다. 

1~100 중에서 하나의 숫자를 생각하고, 상대가 이 숫자를 맞추기 위해서 아무렇게 찍지는 않을 것이다. 

A가 생각한 숫자가 27이었다면, B는 다음과 같이 말할 것이다.

A: 50 ( = (1 + 100) / 2 ) 

B: down

A: 25 ( = (1 + 50) / 2 )

B: up

A: 37 ( = (25 + 50) / 2 )

B: down

A: 31 ( = (25 + 37) / 2 )

B: down

A: 28 ( = (25 + 31) / 2 )

B: down

A: 27 ( = (25 + 28) / 2 )

B: !!!

6번만에 100개의 숫자 중에서 1개의 숫자를 맞췄다. 

 

100이라는 숫자는 2^7(=128)보다 작은 숫자이다. 

이 말은 B가 어떤 숫자를 말하든, 최대 7번 만에 맞출 수 있다는 것이다. 

 

아래 그림처럼 반토막씩 내가 찾고자 하는 대상이 줄어든다.

고등학교 때 나오는 log가 여기에서 나온다.

2^x = 100 와 같은 식은 log로 변환할 수 있다. (로그 2의 100, 아래첨자가 안 되어서 글로 작성했다..)

 

binary search

 

자 이제 코드를 작성하기 위한 개념을 설명해 보겠다. 

1부터 7까지 숫자가 있다고 하자. 

그 중에서 나는 3을 찾고자 한다. 

그러면, 아래 그림을 보기 전에 2^3(=8)이니, 3번 이내에 찾겠구나 라고 생각할 수 있다. 

자 그림을 보면서 생각이 맞았는지 점검해 보자 ^^

 

위 내용을 코드로 선언한다.

int s = 1; // 시작값
int e = 7; // 마지막값
int m = (s + e) / 2; // 중간값
int f = 3; // 목표값

 

s = 1, e = 7, m = 4 로 설정했는데, 

m 값이 우리가 찾는 3이 아니다.

m은 우리가 찾는 3보다 크다.

검색할 대상에서 변화는 값은 end이다. 

e를 m - 1로 설정하고, m를 (s + e) / 2로 설정한다.

코드를 보면 위에서 설명한 up down 게임과 다르다.

e = m - 1 로 설정해야 하지 않는가!!!

위에서는 계산의 편의를 위해서 중간값(m)을 끝값(e)으로 설정했다. 

하지만 컴퓨터가 다 계산해 주니 굳이 그렇게 할 필요가 없다. 

아래 코드를 보라.

if문에서 이미 m 값이 찾는값이 아니라는 것을 알았는데, 다음 검색범위에 포함시킬 필요가 있을까?

while (s <= e)
{
	if (f == m)
	{
		// 찾은 경우
        break;
	}
	else if (f < m)
	{
		// start, end, mid 값을 바꿈
		e = m - 1;	// e = m; 으로 해도 되지만, 우리는 m은 답이 아닌 것을 알고 있음
		m = (s + e) / 2;
	}
	else  
	{
	}
}

 

s = 1, e = 3, m = 2 로 설정했는데,

m 값이 우리가 찾는 3이 아니다.

m은 우리가 찾는 3보다 작다.

검색할 대상에서 변화는 값은 start이다. 

s를 m + 1로 설정하고, m를 (s + e) / 2로 설정한다.  

while (s <= e)
{
	if (f == m)
	{
		// 찾은 경우
        break;
	}
	else if (f < m) 
	{
		// start, end, mid 값을 바꿈
		e = m - 1;	// e = m; 으로 해도 되지만, 우리는 m은 답이 아닌 것을 알고 있음
		m = (s + e) / 2;
	}
	else  // f > m 경우
	{
    	// start, end, mid 값을 바꿈
		s = m + 1; // // s = m; 으로 해도 되지만, 우리는 m은 답이 아닌 것을 알고 있음
		m = (s + e) / 2;
	}
}

 

s = 2, e = 3, m = 2 로 설정했는데,

m 값이 우리가 찾는 3이 아니다.

s = 3, e = 3, m = 3 으로 설정한다.

자, 이제 우리가 찾는 3을 찾았다. 

이미 코드에는 구현되어 있지만, 이 때 반복문을 나오거나 함수를 종료하면 된다. 

 

여기서 의문이 들 수 있다. 

위에서는 3번만에 찾을 수 있다면서 왜 4번이 걸리냐고 생각할 수 있다.

3번까지 하고 사실 우리는 답을 알았다. 

"아~ 남은 3이 답이겠구나" 

근데 컴퓨터는 모른다. 아무 생각이 없다. 

(인공지능이 발달하면 다를 수도 있지만, 지금은 컴퓨터란 녀석은 아무것도 모른다.)

그래서 마지막 하나 남은 너가 맞아? 라고 확인을 한다.

그. 리. 고.

내가 만약에 8을 선택하고 코드를 짰다면, 마지막에 남은 숫자가 답이 아닐 수도 있다.

사람은 8 찾아줘 하는 순간, 

"응 없어~" 하고 끝내지만 컴퓨터는 모른다.

그래서 정확하게는 1 + 로그 2의 N (여기서 N은 주어진 데이터 크기) 정도가 걸린다. 

N이 엄청나게 커지면, 1번 정도 더한다고 오래 걸리지 않으니 말이다. 

100억 자산가에게 1천원, 1만원 느낌이랄까?

 

최종 코드는 아래와 같다.

#include <stdio.h>

int search(int s, int e, int f)
{
	int m;

	while (s <= e)
	{
		m = (s + e) / 2; // m은 f와 같지 않으면 계속 다시 구해야 함으로 조건문에서 뺌

		if (f == m)
		{
			return 1;
		}
		else if (f < m)
		{
			e = m - 1;
		}
		else
		{
			s = m + 1;
		}
	}

	return 0;
}

int main(void)
{
	int s = 1;
	int e = 7;
	int f;
	int ans;


	f = 3;
	ans = search(s, e, f);
	printf("결과: %d\n", ans); //결과: 1

	f = 8;
	ans = search(s, e, f);
	printf("결과: %d\n", ans); //결과: 0

	return 0;
}

 

search()에서 while(s <= e)를 시작하기 전에, f가 s보다 작거나 e보다 크면 return 0을 해서 끝낼 수도 있다. 

사람에 따라서 취향이 코드에 반영이 된다. 

마치 성격처럼 말이다. 

그러니 추가하고 싶거나 삭제해서 코드를 사용하면 된다.