Search in Rotated Sorted Array

문제

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

입력

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10^4 <= target <= 10^4


// 입력 예제

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

결과

ans: Int = target이 위치한 인덱스, 먄약 없다면 -1

해석

이전 문제와 비슷한 이분탐색 문제지만 오름차순의 배열이 회전되어 있어
한번 더 조건을 걸어줘야한다.

 

그 조건은 이분탐색의 필수적인 조건인 정렬 여부, 즉 mid를 중심으로 정렬이 올바르게
되어있는 구간인가 아닌가를  판별

 

또한 mid를 통해 찾을 것이기 때문에, while문의 조건이 < 가 아닌 <= 된다.

코드

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        let n = nums.count

        var start = 0
        var end = n-1

        while start <= end {
            let mid = (start + end) / 2

            if nums[mid] == target { // 찾음
                return mid 
            }

            if nums[start] <= nums[mid]{ // mid까지 오름차순
                if nums[start] <= target && target < nums[mid] { // 왼쪽 범위에 있을 때  
                    end = mid - 1 
                } else {
                    start = mid + 1 
                }
            } else {
                if nums[mid] < target && target <= nums[end] { // end 까지 오름 차순 
                    start = mid + 1
                } else {
                    end = mid - 1
                }
            }
        }
        return -1
    }
}