7244 : 이분탐색 기초
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
이분탐색(Binary Search)은 정렬된 배열에서 특정 원소를 $O(\log N)$ 시간에 찾는 알고리즘입니다.
Python의
[제약 조건]
• 입력되는 모든 수는 정수입니다.
Python의
bisect 모듈 또는 직접 구현한 이분탐색으로 각 쿼리 값이 배열에 존재하는지 확인하십시오.[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정렬된 정수 배열의 크기 $N$과 쿼리 수 $Q$가 주어집니다. ($1 \le N, Q \le 100{,}000$)
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
셋째 줄에 $Q$개의 탐색 대상 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
셋째 줄에 $Q$개의 탐색 대상 정수가 공백으로 구분되어 주어집니다.
출력 설명
각 쿼리 값이 배열 내에 존재하면
1, 존재하지 않으면 0을 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
1 3 5 7 9
3 6 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 0 1도움
bisect_left(arr, x)로 삽입 위치를 구한 후, 해당 위치의 값이 $x$와 같은지 확인합니다. 또는 집합(set)으로 변환하여 $O(1)$로 검색할 수도 있습니다.