[LeetCode] 81. Search in Rotated Sorted Array II - 문제풀이

Description

오름차순으로 정렬된 배열이 알수없는 수만큼 오른쪽으로 rotate된 배열이 있다고 가정할때 target값이 배열에 존재하는지 여부를 반환하는 문제입니다.

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= 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,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= target <= 10^4
• nums is guaranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Solution 1. linear scan

public boolean search(int[] nums, int target) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if(nums[i] == target) return true;
    }
    return false;
}

단순하게 모든 요소를 선형 스캔하여 값을 찾아냅니다.

Solution 2. binary search

public boolean search(int[] nums, int target) {
  int len = nums.length;
  int start = 0;
  int end = len - 1;

  while(start <= end){
      int mid = start + (end - start)/2;
      if(nums[mid] == target) return true;
      
      if(nums[start] < nums[mid]){
          if(target < nums[start] || target > nums[mid]){
              start = mid + 1;
          }else{
              end = mid - 1;
          }
      }else if(nums[start] > nums[mid]){
          if(target < nums[mid] || target > nums[end]){
              end = mid -1;
          }else{
              start = mid + 1;
          }
      }else{

          start ++;
      }
  }
  return false;
}

정렬된 배열을 이진 검색을 통해 값을 찾아 나가는 방법입니다. 포인터 이동시 rotate된 위치를 고려하여 start,end 포인터 위치를 조정해 나갑니다.

Reference

Search in Rotated Sorted Array II - LeetCode