[Java] 33. Search in Rotated Sorted Array

문제 파악

오름차순으로 정렬되어 있는 배열 nums가 있었다.

 

인덱스 k번째 원소가 제일 첫 원소가 되도록 rotated 되어있다.

 

target 이 배열 nums 에 포함되어있는지 O(logN) 으로 탐색하여 인덱스를 반환해야한다.

 

---

풀이

1️⃣ 이분 탐색을 이용한 풀이

💡 떠오른 Idea

먼저, 주어진 시간 복잡도를 만족하기 위해선 이분 탐색을 사용해야함을 알 수 있었다.

결과적으로는, target이 nums에 존재하는지를 이분 탐색해야하는데

특정 값을 탐색하기 위해선 정렬되어있어야 한다.

따라서, rotated된 배열을 정렬된 두개의 배열로 나누기 위해 배열 내의 최솟값을 검색한다.

ex) [4, 5, 6, 7, 0, 1, 2] 배열이 있을 때, [4, 5, 6, 7] 과 [0, 1, 2] 배열 2개로 분리한다. 최솟값인 0 의 위치를 찾아야 분리할 수 있을 것이다.

최솟값은 mid에 위치한 원소가 가장 끝값과 비교했을 때, 오름차순을 유지하고있다면 탐색을 왼쪽 영역으로 이동시키는 방법으로 구할 수 있다. 그 반대라면 오른쪽 영역으로 탐색해야할 것이다.

정렬된 배열 2개로 분리했다면, 이분탐색으로 target 이 존재하는지 확인하면 완료된다.

 

class Solution {
    public int search(int[] nums, int target) {
        int idx = getStartIdx(nums);
        int result1 = findIdx(nums,0,idx-1,target);
        int result2 = findIdx(nums,idx,nums.length-1,target);

        return Math.max(result1,result2);
    }

    private int getStartIdx(int[] nums){
        int left = 0,right = nums.length-1;

        if(nums[left]<=nums[right]){
            return 0;
        }

        while(left<right){
            int mid = (left+right)/2;
            if(nums[mid]<=nums[right]){
                right = mid;
            }else{
                left = mid+1;
            }
        }

        return left;
    }

    private int findIdx(int[] nums, int left, int right,int target){
        while(left<=right){
            int mid = (left + right)/2;
            if(target<nums[mid]){
                right = mid-1;
            }else if(target>nums[mid]){
                left = mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

 

결과

---

📖 회고

정렬되어 있지 않은 배열에서 이분탐색을 사용하기 위한 조건을 떠올리는게 굉장히 까다로운 것 같다.

 

근데, 잘 생각해보면 충분히 떠올릴 수 있는 아이디어들이다.

 

find peak element 문제에서는 mid 값이 mid+1보다 작으면 오른쪽 영역을 탐색하는 방식으로 진행하였고

 

이번 문제의 경우에는 mid 값이 right 값보다 작은 경우, 오른쪽 영역은 오름차순으로 구성되어있음을 보장하므로 왼쪽 영역으로 탐색하는 방식이었다.

 

이러한 이분 탐색 조건들을 잘 찾아낼 수 있도록 고민을 해봐야겠다는 생각이 들었다.