7253 : 회전 정렬 탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
오름차순으로 정렬된 배열이 특정 피벗 위치를 기준으로 회전(Rotate)된 상태에서 타겟 값을 이분탐색으로 찾으십시오.
예:
회전된 배열에서는 좌측 또는 우측 절반이 반드시 정렬된 상태임을 활용합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
예:
[4, 5, 6, 7, 0, 1, 2]는 원래 [0, 1, 2, 4, 5, 6, 7]이 회전된 것입니다.회전된 배열에서는 좌측 또는 우측 절반이 반드시 정렬된 상태임을 활용합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 크기 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 회전된 상태의 배열이 주어집니다.
셋째 줄에 찾는 수 $x$가 주어집니다.
둘째 줄에 회전된 상태의 배열이 주어집니다.
셋째 줄에 찾는 수 $x$가 주어집니다.
출력 설명
$x$가 존재하는 인덱스(0-based)를 출력합니다. 없으면
-1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7
4 5 6 7 0 1 2
0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
mid를 기준으로 좌측 (arr[lo]..arr[mid])이 정렬됐는지 확인합니다. 정렬된 쪽에 타겟이 있으면 그쪽으로 탐색 범위를 좁히고, 없으면 다른 쪽으로 탐색합니다.