변형된 이진검색

정렬된 고유한 정수로 이뤄진 배열과 target 정수가 주어집니다. 주의해야 할 점은 배열에 있는 정수가 Shift 됐다는 것입니다. 다시 말하면, 배열을 절반으로 나눈 후 왼쪽과 오른쪽을 서로 바꾸는 것 입니다. 예를 들어 배열 [1, 2, 3, 4]가 [3, 4, 1, 2]로 바뀌었을 수 있습니다.

변형된 바이너리 검색 알고리즘을 사용하여 target이 배열에 포함되어 있는지 확인하여 target 인덱스를 반환하거나, target이 배열에 없으면, -1을 반환합니다.

예제 1

입력

arr = [45, 61, 71, 72, 73, 0, 1, 21, 33, 37]
target = 33

출력

8