Leetcode 33) Search in Rotated Sorted Array

08 Sep 2021 in Algorithms

내 답안

• 세가지 경우의 수로 나눔

class Solution {
    public int search(int[] nums, int target) {
        // 원래는 mid만 체크했다면, 여기서는 start, end를 다 체크하면될듯?
        int left=0;
        int right= nums.length-1;
        if(right==-1){return -1;}//없을 때
        while(left<=right){
            int mid=left+(right-left)/2; //32integer범위 안넘기 위해서 이렇게 

            if(nums[mid]==target){
                return mid;
            }else if(nums[left]<=nums[mid] && nums[mid]<= nums[right]){
                //정상
                if(nums[mid]<=target){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }else if(nums[left]<nums[mid]){
                if(nums[left]==target){
                    return left;            
                }else if(nums[mid]>target && nums[left]<target){
                    right=mid-1;
                }else{
                    left= mid+1;
                }
            }else{
                if(nums[right]==target){
                    return right;
                }else if(nums[mid]<target && nums[right]>target){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
        }

        return -1;

    }
}

다른 답안

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