[이분 탐색] 이분 탐색(Binary Search) 이란 ?

이분 탐색

 

두 이, 나눌 분을 써서 이분인가?

 

정답, 이분 탐색은 두개로 나누어서 탐색하는 것이다.

예를 들어, 1부터 10까지 있다고 생각해보자.

 

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

 

우리가 8을 찾을 때, 눈으로 바로 보이니까 위치를 파악할 수 있다.

하지만 몇 번째에 있는가? 배열은 0번째부터 시작하니 7번째에 있다는 것을 알 수 있다.

컴퓨터 배열 인덱스 개념이 없는 사람들은 8번째라고 답할 것이다.

즉, O(1) 시간이다.

 

그럼, 
{1, 4, 7, 10, 12, 23, 30, 35, 100, 120} 이 있을 때, 35의 위치는?

우리는 앞에서 값을 세어가면서 몇 번째에 있는지 알 것이다.

즉, O(N) 시간이다.

 

100만개의 숫자가 있다면?

 

우리는 100만개를 일일이 세다가 지루해서 포기한다.

만약에 사람 여러명을 동원해서 숫자를 찾아도 된다면??

 

각 인원들을 100만/N 으로 나누어 각 영역 별로 찾으면 효율적일 것이다.

근데, 각 숫자가 정렬되어 있지 않다면 N이 100만이 될 수도 있다.

즉 O(N)이랑 같은 것이다.

 

만약, 정렬이 되어있다고 생각해보자. 1부터 100만 중 10만을 찾으려는데

번호 하나를 짚었는데 30만이다.

그럼 정렬되어 있기 때문에 우리는 1 부터 30만까지의 영역만 찾으면 된다.

이번에는 9만을 찾았다. 그럼 9만부터 30만까지만 찾으면 된다.

 

이렇게 정렬성을 이용하면 번호를 하나 짚었을 때,

더 큰 값이 있는 쪽과 더 작은 값이 있는 쪽, 2 개의 영역으로 나뉘게 된다.

1. 선택한 숫자가 찾는 값보다 더 작다면 큰 값이 있는 영역

2. 선택한 숫자가 찾는 값보다 더 크다면 작은 값이 있는 영역

두 가지 경우로 나뉘게되는 성질을 이용한 것이 '이분 탐색'이다.

 

---

 

어떻게 구현 하면 될까요?

 

이분 탐색을 알게 되었다면 컴퓨터가 이해할 수 있도록 명령해주어야 한다.

그럼 컴퓨터는 N개의 데이터에 대해 N/2, N/4, N/8 ... O(log N)의 시간복잡도로 원하는 값을 찾게 된다.

 

구현 접근하기

 

임의의 두 영역으로 나누어야 한다. 한 영역을 두 개로 나누기 가장 좋은 방법은 무엇일까?

중간을 기준으로 나누면 된다.

 

이 기준점을 이분 탐색에서 mid 값이라고 한다.

컴퓨터에서 수열을 나타내는 방법은 배열을 이용하므로 우리는 중간 값을 찾을 수 있다.

배열의 시작점 0번 index 부터 끝점 n-1번 index

 

만약 n이 10이라면, mid = (n-1) / 2 = 9 / 2 = 4 가 될 것이다. 

1. 배열이 오름차순이고 4번째 인덱스 값 < key 값 이라면 우리는 5번째 부터 9번까지 찾으면 된다.

즉 시작점이 5번이 되고 끝은 9번이 될 것이다.

 

2. 배열이 오름차순이고 4번째 인덱스 값 > key 값 이라면 우리는 0번째 부터 3번까지 찾으면 된다.

 

3. 배열이 오름차순이고 4번째 인덱스 값 == key 값 이라면 우리는 인덱스 값을 반환해주면 된다.

 

접근을 바탕으로 시뮬레이션 해보기

정렬된 수열의 정보, 찾는 값 62

1. 임의의 한 점 선택 : start = 0, end = 11, mid = (0+11) / 2 = 5

2. 5번에 위치한 값 : 52

3. 52 < 62, s = mid + 1 = 6, e = 11, mid = (6+11) / 2 =  8

4. 8번에 위치한 값 : 61

5. 61 < 62, s = mid + 1 = 9, e = 11, mid = (9+11) / 2 = 10

6. 10번에 위치한 값 : 73

7. 73 > 62, s = 9, e = mid - 1 = 9, mid = (9+9) / 2  = 9

 

7. 9번에 위치한 값 : 62

8. 62 == 62, 9번 반환

 

우리가 생각한대로 시뮬레이션이 성공적으로 된 것을 확인할 수 있다.

 

구현 해보기

 

/*
	authored by jihwankim
	dev-dot.tistory.com
	binary search
*/
#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<int> arr = {
		10, 20, 30, 40, 50, 52, 54, 60, 61, 62, 73, 89
	};
	
	int s = 0, e = arr.size() - 1;
	int key = 62;
	
	while(true) {
		int m = (s+e) / 2;
		if (arr[m] < key) {
			s = m + 1;
		} 
		if (arr[m] > key) {
			e = m - 1;
		}
		if (arr[m] == key) {
			cout << key << "는 " << m+1 << "번 째에 있습니다.\n";
			break;
		}
	}
	return 0;
}

 

원하는 결과 값이 나온 것을 확인할 수 있다.

 

추천 Thinking

 

1. 재귀로 접근해보기

2. 좀 더 좋은 방법이 있다면 생각해보기