1. 분할정복 - 이분 탐색

이분탐색이란?

이분탐색은 어떤 기준으로 정렬이 된 수열에서 원하는 원소를 찾을 때 사용하는 방법이다. 주어진 수열에서 중간 값을 기준으로 찾는 값이 중간 값보다 작으면 처음 ~ 찾는 값까지 탐색하고 찾는 값이 중간 값보다 크면 중간 값 ~ 끝 값을 탐색하는 형태로 진행한다. 이것은 분할-정복 알고리즘을 사용한 형태로 큰 문제에서 작은 문제로 결과를 줄여나가 원하는 값을 얻어내는 형태이다. 

 

예시는 다음과 같다.

ex.) 주어진 값 : 1 3 4 5 8 12 15 20 24 30 49, 찾는 값 : 30,

1. 1 3 4 5 8 12 15 20 24 30 49 -> 중간 인덱스는 11/ 2 = 5이고 중간 값은 12이다. 12 < 24이니까 12이하는 사용X

2. 15 20 24 30 49 -> 중간 인덱스는 5 / 2 = 2이고 중간 값은 24이다. 24 < 30이니까 24이하는 사용X

3. 30 49 -> 중간 인덱스는 2 / 2 = 1이고 중간 값은 49이다. 49 > 30이니까 49이상은 사용X

4. 30 -> 중간 인덱스는 1 / 2 = 0이고 중간 값은 30이다. 30을 찾았다.

재귀호출로 설계 vs 반복문으로 설계

이분 탐색은 재귀호출을 사용하는 방법과 반복문을 사용하는 방법이 있다. 재귀 호출을 이용할 경우 함수를 메모리에 담아 놓는다. 이것은 메모리 초과로 이어질 수 있기 때문에 반복문을 이용하여 이분 탐색을 사용하길 바란다.

 

시간복잡도

이분 탐색은 선형 탐색보다 시간 복잡도가 작다. 처음부터 찾지 않고 구간을 나누어 찾기 때문에 모든 숫자를 각각 비교하지 않아도 되기 때문이다. 이러한 장점으로 일반적인 이분 탐색의 시간 복잡도는 O(logn)이다. 

 

구현

다음은 이분탐색을 재귀호출과 반복문을 이용하여 이분탐색을 구현한 것이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> v;
int rec_where = -1;

//1. 재귀호출로 이용한 이분탐색
int func(int n, int m, int x) { //시작 인덱스, 끝 인덱스, 찾는 값
	int mid = (n + m) / 2;
	if (n > m) { //찾을 수 있는 범위를 넘어간 경우
		return rec_where;
	}
	if (x == v[mid]) { //중간 값이 원하는 값인 경우 경우
		rec_where = mid + 1; //1번째부터 시작이라고 가정하여 +1을 한 값으로 반환
		return rec_where;
	}
	else if (x < v[mid]) { //중간 값이 원하는 값보다 큰 경우
		return func(n, mid - 1, x);
	}
	else { //중간 값이 원하는 값보다 작은 경우
		return func(mid + 1, m, x);
	}
}

int main() {
	int x = 12; //찾는 값

	v.push_back(1);
	v.push_back(10);
	v.push_back(2);
	v.push_back(40);
	v.push_back(100);
	v.push_back(340);
	v.push_back(12);
	v.push_back(3);
	v.push_back(35);
	v.push_back(1000);
	v.push_back(59);
    
	sort(v.begin(), v.end());

	func(0, v.size() - 1, x);

	//2. 반복문을 이용한 이분탐색
	int n = 0; //시작 인덱스
	int m = v.size() - 1; //끝 인덱스
	int iter_where = -1; //찾는 위치
	while (n <= m) {
		int mid = (n + m) / 2;
		if (v[mid] == x) { //중간 값이 원하는 값인 경우 경우
			iter_where = mid + 1; //1번째부터 시작이라고 가정하여 +1을 한 값으로 반환
			break;
		}
		else if (x < v[mid]) { //중간 값이 원하는 값보다 큰 경우
			m = mid - 1;
		}
		else { //중간 값이 원하는 값보다 작은 경우
			n = mid + 1;
		}
	}

	if (rec_where == -1) {
		cout << "재귀 호출로 못 찾음" << '\n';
	}
	else {
		cout << "재귀 호출 : " << rec_where << "번째" << '\n';
	}

	if (iter_where == -1) {
		cout << "반복문으로 못 찾음" << '\n';
	}
	else {
		cout << "반복문 : " << iter_where << "번째" << '\n';
	}
}

 

다음은 결과이다.