7237 : 정렬 후 이진탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수 배열과 $Q$개의 질의가 주어질 때, 각 질의 값 $x$에 대해 $x$ 이상인 원소가 처음 등장하는 위치(Lower Bound)를 구하십시오.
배열을 먼저 정렬한 후 이진탐색을 적용하면 $O((N+Q)\log N)$ 시간에 해결할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
배열을 먼저 정렬한 후 이진탐색을 적용하면 $O((N+Q)\log N)$ 시간에 해결할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 배열의 크기 $N$과 질의 수 $Q$가 주어집니다. ($1 \le N, Q \le 100{,}000$)
둘째 줄에 $N$개의 정수가 주어집니다.
셋째 줄부터 $Q$개의 줄에 찾고자 하는 수 $x$가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
셋째 줄부터 $Q$개의 줄에 찾고자 하는 수 $x$가 주어집니다.
출력 설명
각 질의에 대해 $x$ 이상인 원소가 처음 등장하는 인덱스(1-based)를 출력합니다.
해당하는 원소가 없으면 -1을 출력합니다.
해당하는 원소가 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
3 1 4 1 5
1
3
6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
3
-1도움
Python의
bisect.bisect_left(arr, x)를 사용하면 편리합니다. 반환값이 $N$이면 해당하는 원소가 없어 -1을 출력합니다.