Daily Algorithm - Search in Rotated Sorted Array

Description

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.

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000
• 104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• 104 <= target <= 104

Solution

• O(log n)의 시간복잡도로 구현하기 위해서는 이진 탐색으로 풀어야 한다.
• 하지만 그것보다 중요한 것은 어떤 조건일때 왼쪽과 오른쪽 인덱스를 옮겨야하는지를 꼼꼼히 정리하는것 같다.
• 우선 크게 두가지 경우로 나누어 생각한다. 왼쪽이 정렬된 상태인 경우와 오른쪽이 정렬된 상태인 경우. 그리고 그 안에서 오른쪽을 탐색해야 하는 경우, 왼쪽을 탐색해야 하는 경우가 나뉜다.
  • 가운데 인덱스 기준 왼쪽이 정렬된 상태 : [4, 5, 6, 7, 8, 0, 1, 2]
    • 오른쪽 탐색 (target = 0 || target = 8) : target < nums[l] || nums[m] < target
    • 왼쪽 탐색 (target = 6) : 위를 제외한 나머지 케이스
  • 가운데 인덱스 기준 오른쪽이 정렬된 상태 : [5, 6, 0, 1, 2, 3 ,4]
    • 오른쪽 탐색 (target = 2) : nums[m] < target ≤ nums[r]
    • 왼쪽 탐색 (target = 0) : 위를 제외한 나머지 케이스

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var l = 0
        var r = nums.lastIndex
        
        while (l <= r) {
            val m = (l + r) / 2
            if (target == nums[m]) return m
            
            if (nums[l] <= nums[m]) { // left sorted
                if (target < nums[l] || nums[m] < target) { // search right
                    l = m + 1
                } else { // search left
                    r = m - 1
                } 
            } else { // right sorted
                if (nums[m] < target && target <= nums[r]) { // search right
                    l = m + 1
                } else { // search left
                    r = m - 1
                }
            }
        }
        
        return -1
    }
}