1920 백준

A안에서 X의 존재 여부를 출력하는 문제

N과 M의 크기는 10^5, 모든 정수 범위는 int형

그냥 하나하나씩 찾으면 10^10이니까 N의 input에 대해 정렬하고 각 M의 원소에 대하여 binary search하면 될 것같다.

 

 

 

13분, 좀 더 줄이자.

굳이 binary search구현 할 필요 없이

1. lower_bound를 이용하여 가장 근접한 작은 값의 인덱스를 찾고 값비교 하면 더 빠르고 쉽다.

 

algorithm에 정의된 lower_bound를 보면

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

이미 정렬된 곳에서 comp보다 작지 않은 첫 원소의 iterator를 리턴한다.

 

2. 혹은 그냥 map을 이용해서 find 이용하면 훨씬 더 쉽다.