정렬된 배열에서 원하는 수 탐색 - 이진 탐색 알고리즘

만약 정렬이 되어있지 않은 1~n까지의 숫자가 들어있는 (중복없이) 크기 n의 배열이 있다고 가정했을 때, 

우리가 원하는 임의의 숫자 k의 위치를 찾기 위해선 앞쪽부터 하나씩 탐색해야한다. 

 

만약 최악의 경우는 k가 맨 뒤에 있을 경우인데, 그 경우 우리는 크기의 n의 배열에서 n번 (모두) 확인해야한다.

 

n의 크기가 크지 않거나, 한번만 수행하면 될 경우에는 나쁘지않은 방법일 수도 있다.

 

하지만 반대로, n의 크기가 매우 크고, k, m, n, l 등 여러 개의 숫자의 위치를 찾아야 한다면, 

배열을 정렬한 뒤에 O(logn)의 시간 내에 탐색이 가능하다.

 

여기에선 배열을 정렬하는 방법 자체에는 집중하지 않는다. 

 

방식은 간단하다 크기 10000인 배열에서 내가 찾고 싶은 수가 100번 째에 있다고 가정하면,

먼저 가운데 5000번째 인덱스를 확인해본다. 배열은 크기 순으로 정렬되어 있기 때문에,  5000번째 배열이 찾고자 하는 수보다 크다면 우리가 찾고자 하는 수는 5000보다 작은 인덱스에 들어있다는 것을 알 수 있다.

그렇기 때문에 다음에는 절반인 2500을 탐색한다. 그리고 다음엔 1250을 탐색한다...

 

이런식으로 원하는 숫자가 들어있을 범위를 반으로 줄여나가기 때문에, log시간 내에 탐색이 가능하다.

---

#include <iostream>
using namespace std;

int main() {
	for (int target = 1; target < 100000; target++) {
		int count = 0;
		int n = 100000;
		int a = 0;
		n = n / 2;
		a = a + n;
		while (true) {
			count++;
			if (n % 2 == 0)
				n = n / 2;
			else n = n / 2 + 1;

			if (a < target) {
				a = a + n;
			}
			else {
				a = a - n;
			}
			if (a == target) break;
		}
		cout << endl;
		cout << "count: " << count;
	}
}

위의 코드를 통해보면, 100000개의 숫자 중에 원하는 숫자(target)이 1부터 ~99999까지 증가할 때 몇 번 시도해서 찾아내는지를 알 수 있다.

 

중요한 점은 n의 값 (탐색 폭)이 절반씩 줄어든다는 점이다.

 

만약 순서가 정렬이 되어있지 않아서, 앞에서부터 차례로 일일이 탐색한다면,  약 평균 5만번 정도를 확인해야한다.

 

---

실행결과:

 

100000개의 원소 중에 원하는 원소를 약 15번 전후로 찾아낼 수 있다.