1.2.2 이진 탐색(Binary Search)

벡터의 크기, 탐색 대상, 벡터의 원소들을 입력 받아 이진탐색 결과 탐색 대상이 벡터에 존재한다면 상응하는 인덱스를, 존재하지 않는다면 -1을 반환한다.

 

입력 방식에는 임의로 벡터를 생성하는 RAND_INUT과 표준입출력으로 벡터를 생성하는 STD_INPUT이 있다. 두 입력 방식은 동시에 사용할 수 없으며, 전자가 기본값으로 설정되어 있다. 후자를 사용하기 위해서는 맨 윗줄 #define RAND_INPUT를 주석처리해서 #define STD_INPUT을 활성화시키면 된다.

 

탐색 방식에는 ITER_SEARCH와 RECUR_SEARCH있다. 각각 반복과 재귀 방식으로 탐색한다. 두 탐색 방식은 함께 사용할 수 있기 때문에 #ifndef로 상호배제하지 않도록 했으며, 둘 다 사용하는 것이 기본값이다. #define ITER_SEARCH, #define RECUR_SEARCH 중에 사용하고 싶은 것을 그대로 두고, 그렇지 않은 것을 주석처리하면 된다. 둘 다 주석처리하면 어떠한 탐색도 수행되지 않으며 결과 값도 출력되지 않는다.

#define RAND_INPUT
#ifndef RAND_INPUT
#define STD_INPUT
#endif

#define ITER_SEARCH
#define RECUR_SEARCH

#include <iostream>
#include <vector>
#include <algorithm>

#ifdef RAND_INPUT
#include <cstdlib>
#include <ctime>
#include <unordered_set>
#define MAX_N 10
#define MIN_N 5
#define MAX_n 20
#endif

using namespace std;

int N, K, n;	// 벡터의 크기, 찾을 숫자, 벡터의 원소
int l, m, r;	// 탐색 인덱스 하한, 중앙값, 상한
vector<int> v;	// 벡터

#ifdef RAND_INPUT
unordered_set<int> set;
#endif

#ifdef ITER_SEARCH
int binSearch_iter() {
	l = 0; r = N - 1;
	while (l <= r) {
		m = (l + r) / 2;
		if (v[m] < K) {
			l = m + 1;
		}
		else if (K < v[m]) {
			r = m - 1;
		}
		else
			return m;
	}
	return -1;
}
#endif

#ifdef RECUR_SEARCH
int binSearch_recur(int l, int r) {
	if (l > r)
		return -1;

	m = (r + l) / 2;
	if (v[m] < K) {
		return binSearch_recur(m + 1, r);
	}
	else if (K < v[m]) {
		return binSearch_recur(l, m - 1);
	}
	else
		return m;
}
#endif

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
#if defined STD_INPUT
	cin >> N >> K;
	for(int i = 0; i < N; ++i) {
		cin >> n;
		v.push_back(n);
	}
#elif defined RAND_INPUT
	srand(time(0));
	N = rand() % (MAX_N - MIN_N + 1) + MIN_N;
	K = rand() % MAX_n + 1;
	for (int i = 0; i < N; ++i) {
		do {
			n = rand() % MAX_n + 1;			
		} while (set.find(n) != set.end());
		set.emplace(n);
	}

	for (auto n : set)
		v.push_back(n);
	sort(v.begin(), v.end());
#endif

	cout << "sample input : \n";
	cout << "array size, key\n";
	cout << "array elements\n\n";

	cout << "input : \n";
	cout << N << ' ' << K << '\n';
	for (auto n : v)
		cout << n << ' ';
	cout << "\n\n";

	cout << "answer : \n";
#ifdef ITER_SEARCH
	cout << "iterative :\t" << binSearch_iter() << '\n';
#endif
#ifdef RECUR_SEARCH
	cout << "recursive :\t" << binSearch_recur(0, N - 1) << '\n';
#endif
	return 0;
}