7248 : 이분탐색 직접 구현
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
이분탐색을
탐색 과정에서 방문한 미드포인트(mid)의 값들을 순서대로 기록하고, 최종적으로 타겟의 인덱스를 출력합니다.
탐색 과정을 추적함으로써 이분탐색의 동작 원리를 깊이 이해할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
while lo <= hi 구조로 직접 구현하십시오.탐색 과정에서 방문한 미드포인트(mid)의 값들을 순서대로 기록하고, 최종적으로 타겟의 인덱스를 출력합니다.
탐색 과정을 추적함으로써 이분탐색의 동작 원리를 깊이 이해할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 배열의 크기 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
셋째 줄에 타겟 값 $T$가 주어집니다.
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
셋째 줄에 타겟 값 $T$가 주어집니다.
출력 설명
탐색 도중 방문한 미드포인트(mid)의 값들을 줄바꿈으로 출력합니다.
마지막 줄에 타겟 값의 인덱스(0-based)를 출력합니다. 없을 경우 -1을 출력합니다.
마지막 줄에 타겟 값의 인덱스(0-based)를 출력합니다. 없을 경우 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7
1 3 5 7 9 11 13
7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7
3도움
mid = (lo + hi) // 2를 계산할 때마다 arr[mid]를 출력 목록에 추가합니다. 오버플로우 방지를 위해 lo + (hi - lo) // 2를 사용할 수 있습니다.