Search Rotated Array

임의의 수만큼 오른쪽으로 회전된 소트 끝난 배열과, 지정된 수(key)가 건네져 검색합니다.

설명

임의의 수만큼 회전된 소트 끝난 배열로, 지정된 수(key)를 검색합니다. Key 가 존재하지 않는 경우는 -1 을 돌려줍니다. 배열에 중복이 포함되어 있지 않다고 가정합니다.
다음은 회전 전의 원래 배열입니다.

이 배열에서 6회 회전을 실행하면 다음과 같이 바뀝니다.

조건

선형 검색 O(n)은 허용되지 않는 솔루션입니다.

수정한 Binary Search를 생각한다.

Solution

Runtime Complexity O(logn)

Binary Search를 이용하고 있다.

Memory Complexity O (logn).

한번의 루프마다, 건네받은 Array를 반으로 자르고, 한쪽만으로 검색을 걸고 있다.

해설

해결책은 기본적으로 Binary Search이지만 몇 가지 수정 사항이 추가되었습니다. 예제의 배열을 살펴보면 배열의 최소 절반이 항상 정렬되어 있음을 알 수 있습니다. 이 특징을 이용합니다. 원하는 숫자 n이 배열의 정렬 된 절반에 있으면 Binary Search에서 찾을 수 있습니다. 그렇지 않으면 정렬된 절반을 버리고 정렬되지 않은 절반을 계속 검사합니다. 각 단계에서 배열을 절반으로 나누기 때문에 Runtime Complexity는 O(logn)가 됩니다.
코드에서 조금 읽기 어려운 조건부 부분이 있습니다. 네 가지 조건에서
1. 반으로 자른 start ~ mid 의 범위의 SubArray 가 소트 되고 있는 한편, 찾고 있는 Key 가 그 범위에 존재할 때.
2. 반으로 자른 mid ~ end 범위의 SubArray 가 소트 되고 있고, 찾고 있는 Key 가 그 범위에 존재할 때.
3. 절반으로 자른 start ~ mid 범위의 SubArray 가 소트되지 않고, 한편, 찾고 있는 Key 가 그 범위에 존재할 때.
4. 절반으로 자른 mid ~ end 범위의 SubArray 가 정렬되지 않고, 한편, 찾고 있는 Key 가 그 범위에 존재할 때.
라고 말하는 대로 조건 나누고 있습니다.

구현

테스트

출력