33. Search in Rotated Sorted Array

문제

• 회전된 배열에서 target 넘버 찾기
• 넘버가 없으면 -1의 값을 리턴
• 런타임이 O (log n)이 되야함

해결방법

• Modified Binary Search

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right){
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]){
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[right]){
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

어떤 Search 알고리즘을 사용해야 하는지 결정하는데 어렵지는 않았지만 어떻게 수정해야 할지 고민이 됐던 문제다. Binary Search의 Mid 값을 수정하는 것처럼 두 가지의 케이스가 크게 있지만 여기서 제일 중요한건 target의 값으로 right과 left를 수정하는건 케이스 안에 있다.

 

큰 케이스는 mid가 left보다 크냐 작냐로 나뉘어지는데 이건 배열이 rotate이 됨에 따라서 in order 상태가 아니기 때문. 그래서 크게 Mid의 값으로 케이스를 만들고 또 그 안에서 target으로 left를 +1 해주냐 right -1 해주냐를 나눴다.