# 33. Search in Rotated Sorted Array
#### Difficulty: Medium
link: https://leetcode.com/problems/search-in-rotated-sorted-array/

### 1. Binary Search
#### $O(log\ n)$ runtime, $O(1)$ space

題目限制$O(log\ n)$複雜度，所以想到用binary search，套用binary search模板。

由於條件比較複雜，先討論各種情況。
##### python

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

簡化版如下。
##### python

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

討論區的想法很棒，把rotated過的部分視為inf和-inf，參考[這篇](https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14435/Clever-idea-making-it-simple)。
* If target is let's say 14, then we adjust nums to this, where "inf" means infinity:
* [12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
* If target is let's say 7, then we adjust nums to this:
* [-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

###### tags: `leetcode`