LeetCode) 33. Search in Rotated Sorted Array

33. Search in Rotated Sorted Array

153번 문제와 매우 유사한 문제이다. 153번 문제에서는 회전하기 전의 첫번째 인덱스를 찾는 문제라면 이번문제는 회전되는것은 똑같지만 target이 되는 값이 있는지를 확인하는 문제이다. 똑같이 O(log n)의 복잡도를 가지고 있어야한다.

처음에는 이분탐색을 할 때 처음부터 조건을 나눠서 구하는 방법을 생각했는데 이분탐색을 두번 시행하면 시간복잡도가 O(2long N) 이므로 상수는 제거되므로 log n이 된다!!!

그래서 중간 값을 찾고 그 값을 통해서 범위를 재설정하면 된다.

class Solution {

    public int findMid(int[] nums){
        int start = 0;
        int end = nums.length -1;

        while(start < end){
            int mid = start + (end - start) / 2;

            if(nums[mid] > nums[end]){
                start = mid + 1;
            }else if(nums[mid] < nums[end]){
                end = mid;
            }
        }

        return start;
    }

    public int findTarget(int[] nums,int start,int end,int target){
        
        while(start <= end){
            int mid = start + (end - start) / 2;

            if(nums[mid] > target){
                end = mid-1;
            }else if(nums[mid] < target){
                start = mid + 1;
            }else{
                return mid;
            }
        }

        return -1;
    }


    public int search(int[] nums, int target) {
        
        int change = findMid(nums);

        int start;
        int end;

        if(change == 0){
            start = 0;
            end = nums.length -1;
        }else if(target >= nums[0] && target <= nums[change -1]){
            start = 0;
            end = change -1;
        }else{
            start = change;
            end = nums.length -1;
        }
        return findTarget(nums,start,end,target);
    }
}