[문제풀이] Leetcode 33. Search in Rotated Sorted Array 자바 풀이

👉 문제

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]. 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.

입출력 예시:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Input: nums = [1], target = 0
Output: -1

✨ 풀이

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length-1, target);
    }
    public int binarySearch(int[] nums, int start, int end, int target) {
        if(start >= end) {
            return (nums[start] == target) ? start : -1;
        }
        int temp = -1;
        int mid = (start + end) / 2;
        if(nums[mid] == target){
            temp = mid;
        } else {
            temp = binarySearch(nums, start, mid-1, target);
                if(temp < 0) {
                    temp = binarySearch(nums,  mid+1, end, target);
                }
        } return temp;
    } 
}

풀이 노트:

• 이진 탐색 응용 문제로, O(log n)의 복잡도를 가져야 하기 때문에 전부 순회하는 방식이 아니라 어떠한 기준에 따라 배열을 앞, 뒤 두 파트로 나눠서 탐색해야 한다.

• 기본 이진 탐색은 보통 중간 인덱스의 값이 target 보다 크거나 작은 기준으로 탐색 범위를 좁혀간다. 따라서 오름차순으로 정렬된 배열에서는 이런 비교를 통해서 탐색하면 정확하게 값에 도달할 수 있다.

• 그러나 이 문제의 경우 주어지는 배열이 회전되었기 때문에, 한 기준점으로 배열을 딱 잘라 한 쪽만 좁혀가는 건 올바르지 않다. 대신 조금 변형해서 mid값을 두되, temp 라는 값을 기준으로 배열을 잘라서 이진 탐색한다.

• start >= end의 조건을 둔 이유는 길이가 1인 배열이 들어올 수도 있기 때문이다.