실습 2주차 [2] Binary Search

문제

10^6개 만큼의 서로 다른 unsigned integer가 정렬된 형태로 input에 들어오고, 다음으로는 10^4개 만큼의 서로 다른 unsigned integer가 들어온다.

이 때 처음의 10^6개의 데이터는 배열에 들어가며, 그 다음 input인 10^4개의 데이터에 대해서 binary search를 이용해서 해당하는 인덱스를 반환해서 각각 출력하게 한다.

만약 해당하는 값이 없는 경우에는 -1을 반환한다.

입력 형식

숫자1 숫자2 ... 숫자1000000

숫자1 숫자2 ... 숫자10000

출력 형식 : 인덱스 값을 한 줄에 하나씩 찍도록 한다. 즉 찾는 값이 총 10^4개이므로 출력은 10^4줄에 걸쳐서 나와야 한다.

답안

#include <iostream>

using namespace std;

#define SIZE 1000000

int binarySearch(unsigned int[], int, int, unsigned int);

int main(){
	unsigned int arr[SIZE];
	unsigned int x;
	for (int i = 0; i < SIZE; i++)
		cin >> arr[i];
	for (int i = 0; i < 10000; i++){
		cin >> x;
		cout << binarySearch(arr, 0, SIZE - 1, x) << endl;
	}
}

int binarySearch(unsigned int arr[], int i, int j, unsigned int k){
	if (i > j)
		return -1;
	if (i == j){
		if (arr[i] == k)
			return i;
		else
			return -1;
	}
	int mid = (i + j) / 2;
	if (arr[mid] == k){
		return mid;
	}
	else if (arr[mid] > k){
		return binarySearch(arr, i, mid - 1, k);
	}
	else {
		return binarySearch(arr, mid + 1, j, k);
	}
}