[백준-20551] Sort 마스터 배지훈의 후계자

<문제>

---

<Code>

//20551] Sort 마스터 배지훈의 후계자 
//Binary Search
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	freopen("input.txt","rt", stdin);
	int n, m, tmp, res;
	scanf("%d %d", &n, &m);
	vector<int> v;
	
	for(int i=0; i<n; i++){
		scanf("%d", &tmp);
		v.push_back(tmp);
	}
	sort(v.begin(), v.end());
	
	for(int j=0; j<m; j++){
		scanf("%d", &tmp);

		//찾아낸 위치의 주소를 리턴하므로 v.begin()(첫번째 원소의 주소)을 빼야함.
		res=lower_bound(v.begin(), v.end(), tmp)-v.begin();
		
		if(v[res]==tmp && res!=n){
			printf("%d\n",res);
		}else{
			printf("-1\n");
		}
		
	}
	
	/* 시간좀 생각해^^ 
	for(int i=0; i<m; i++){
		scanf("%d", &tmp);
		auto it=find(v.begin(), v.end(), tmp);
		if(it==v.end()){
			printf("-1\n");
		}else{
			printf("%d\n", it-v.begin());
		}		
	}
	*/
	return 0;
}

---

<Comment>

처음엔 문제 읽자마자 find()로 찾아서 인덱스번호 출력하면 되는줄 알고 생각없이(?) 호다닥 써서 제출했는데 시간초과

-> Binary Search(이분탐색)을 이용해서 찾아야 함.

1. 벡터에 넣어서 정렬해주고
2. 이분탐색으로 위치를 찾아야 하는데, "처음으로 등장한 위치"를 찾아야 하므로 lower_bound를 사용.

---

https://www.acmicpc.net/problem/20551

20551번: Sort 마스터 배지훈의 후계자