[LeetCode] 33. Search in Rotated Sorted Array

 

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Search in Rotated Sorted Array - LeetCode

문제 유형 : 이진 탐색

문제 난이도 : Medium

 

문제

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

 

정해진 값만큼 회전된 배열 nums와 찾으려는 값 target이 있다. 얼마나 회전되어있는지는 알 수 없다.

target이 위치한 인덱스를 반환하고, 없으면 -1을 반환하라. O(log n)의 시간 복잡도를 가져야 한다.

 

풀이

1. 무식하게 풀기 - 선형적인 탐색

배열의 양 끝을 target과 비교해본다.

target이 nums[0]보다 작다면, 배열을 거꾸로 탐색하고,

만약 크다면 정순으로 탐색한다.

만약 거꾸로 탐색하는 중에 target이 nums[i]보다 크거나, 회전하기 이전의 배열의 양 끝(배열의 최댓값과 최솟값)이 감지된다면 탐색을 그만두고 -1을 반환한다. target값을 nums에서 찾으면 그 인덱스를 반환한다.

반대도 같다.

탐색하는 중에 target이 nums[i]보다 작거나, 회전하기 이전의 배열의 양 끝을 감지하면 탐색을 그만두고 -1을 반환한다. target값을 nums에서 찾으면 그 인덱스를 반환한다.

 

2. 문제의 목적에 맞는 풀이 - 이진탐색

사실 문제에서 O(log n)을 보자마자 이진 탐색으로 푸는것이라고 생각이 들었다.

왼쪽 끝을 left, 오른쪽 끝을 right, 두 지점의 중간을 mid로 설정한다.

 

아래 루프를 반복한다 : 

  nums[mid]가 target과 같다면, mid를 반환.

 

  만약 nums[left]가 nums[mid]보다 작다면: (mid가 회전된 부분의 경계를 넘지 않았다는 뜻)

    목표값이 왼쪽 부분에 있다고 판단되면:

      right을 mid-1으로 설정한다.

    그 반대라면

      left를 mid+1로 설정한다.

  만약 nums[left]보다 nums[mid]가 작다면, mid는 회전된 부분 이후로 넘어왔다는 뜻이다.

    목표값이 오른쪽 부분에 있다고 판단되면:

      left을 mid+1으로 설정한다.

    그 반대라면

      right를 mid-1로 설정한다.

 

코드

1. 선형적인 탐색

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        const int n = nums.size();
        
        if(target == nums[n-1]) return n-1;

        if(target < nums[0]){
            for(int i = n-1; i > 0; i--){
                if(target == nums[i]) return i;
                if(nums[i] < nums[i-1] || nums[i] < target) break;
            }
        }
        else if(target == nums[0]){
            return 0;
        }
        else{
            for(int i = 0; i < n-1; i++){
                if(target == nums[i]) return i;
                if(nums[i] > nums[i+1] || target < nums[i]) break;
            }
        }

        return -1;
    }
};

 

2. 이진 탐색

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        
        while (left <= right) {
            int mid = (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 (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
};

 

python3

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

 

Dart

class Solution {
  int search(List<int> nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
      int mid = (left + right) ~/ 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 (nums[mid] < target && target <= nums[right]) {
          left = mid + 1;
        } 
        else {
          right = mid - 1;
        }
      }
    }
    return -1;
  }
}

 

Java

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

 

Swift

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        while left <= right {
            var mid = (left + right) / 2
            if nums[mid] == target{
                return mid
            }

            if nums[left] <= nums[mid] {
                if nums[left] <= target && nums[mid] > target { 
                    right = mid-1
                }
                else {
                    left = mid+1
                }
            }
            else {
                if nums[right] >= target && nums[mid] < target {
                    left = mid+1
                }
                else {
                    right = mid-1
                }
            }
            
        }
        return -1
    }
}

 

 

여담(..)

C++기준 두 방법의 런타임 차이는 없었다..!

아무래도 선형 탐색 도중에 더 탐색할 필요가 없는 케이스에서 멈추게 설계해놔서 그런 듯 하다.