문제

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

제한사항

• 1 <= nums.length <= 5000
• $-10^4$ <= nums[i] <= $-10^4$
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• $-10^4$ <= target <= $10^4$

접근

이분탐색 응용 문제였어요. 특정 부분 배열의 순서가 역전이 된 경우에 대한 target의 위치를 찾는 문제였습니다. $log(n)$의 속도로 찾으라 했으니, 역전된 부분을 순회해서 찾는건 불가능한 문제니까 결국엔 이분 탐색의 기준을 살짝 바꿔,

1. 중간 값 == target일 경우 반환
2. start ~ mid - 1부분 이분 탐색
3. target을 못찾으면 mid + 1 ~ end부분 이분 탐색

기존 이분 탐색은 target보다 작으면 우측만, target보다 크면 좌측만 탐색하면 되는 방식을 조금 다르게 수정하니 매우 안정적으로 해결이 되었습니다.

답안

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }

    private int binarySearch(int[] nums, int start, int end, int target) {
        if(start >= end)
            return (nums[start] == target) ? start : -1;

        int ret = -1;
        int mid = (start + end) >>> 1;
        if(nums[mid] == target){
            ret = mid;
        } else{
            ret = binarySearch(nums, start, mid - 1, target);
            if(ret < 0)
                ret = binarySearch(nums, mid + 1, end, target);
        }

        return ret;
    }
}