문제1909--Binary search

1909: Binary search

실행시간 제한: 5 Sec  메모리사용 제한: 256 MB
제출: 457  통과: 228
[제출] [채점기록] [묻고답하기]

문제 설명

오름차순 정렬이 된 정수로 이뤄진 배열 $A$가 주어질 때, 임의의 숫자 $X$를 입력받아 $X$가 $A$의 몇번째에 존재하는지 검색하는 프로그램을 작성하라. 검색은 프로그램이 실행되는 동안 여러번 이뤄진다.

 

입력 설명

입력의 첫줄에는 배열의 크기 $N$이 입력되며, 그 다음줄에는 오름차순으로 정렬된 $N$개의 숫자가 입력된다.

다음에는 검색하려는 횟수를 뜻하는 $Q$가 입력되며, 그 다음 부터 $Q$개의 정수가 한줄에 하나씩 입력된다.

제약조건

  • $ 1 \leq N \leq 100000 $
  • $ 1 \leq Q \leq 10000 $
  • 모든 정수는 0 이상 2^31 - 1이하의 정수다.

출력 설명

검색하려는 숫자가 배열 $A$에 존재할 경우 배열 $A$에서의 위치를 출력하며, 그렇지 않을 경우 $-1$을 출력한다. 배열의 맨 앞의 원소의 위치는 0이며, 그다음은 $1, \dots $마지막은 $N$-1이다.

입력 예시 Copy

5
1 3 4 5 7
4
4
1
6
8

출력 예시 Copy

2
0
-1
-1

출처/분류