[파이썬 PYTHON · 자바 JAVA] LeetCode【Search in Rotated Sorted Array】

 

Search in Rotated Sorted Array - LeetCode

---

자바 코드

class Solution {
    public int search(int[] nums, int target) {
        int idx = findMin(nums);
        int findL = findIdx(nums,0,idx-1,target);
        int findR = findIdx(nums,idx,nums.length-1,target);

        return Math.max(findL,findR);
    }

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

    public int findMin(int[] nums){
        int left = 0;
        int right = nums.length-1;

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

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

파이썬 코드

class Solution(object):
    def search(self, nums, target):
        idx = self.findMin(nums)
        findL = self.findIdx(nums,0,idx-1,target)
        findR = self.findIdx(nums,idx,len(nums)-1,target)
        return max(findL,findR)


    def findIdx(self,nums,left,right,target):
        while left<=right:
            mid = (left+right)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid+1
            else:
                right = mid -1
        return -1

    def findMin(self,nums):
        left = 0
        right = len(nums)-1
        
        if nums[left] <= nums[right]:
            return 0;

        while left<right:
            mid = (left+right)//2
            if nums[mid]>nums[right]:
                left = mid+1
            else:
                right = mid
        return left

 

이분탐색으로 회전되어 있는 오름차순 배열을 오름차순 정렬되어있는 2개의 배열로 나눈다.

 

[4,5,6,7,0,1,2] 배열이 주어진다면

 

findMin() 함수는 

오름차순이 시작되는 값의 인덱스를 구하는 함수이다.

 

즉, 4가 반환될 것이다.

 

그려면 그 인덱스를 기준으로, [4,5,6,7] 과 [0,1,2] 로 분리할 수 있고

 

오름차순 되어있는 두 배열에서 target 값을 찾기 위한 이분탐색을 한번 더 하면 된다.