---
description: LeetCode 33
---

# Search in Rotated Sorted Array

```python
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        """
        找尋target第一個出現的位置
        """
        lo = 0
        hi = len(nums) - 1
        firstRes = -1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if target == nums[mid]:
                firstRes = mid
            while mid < hi and nums[mid] == nums[hi]:
                hi = hi - 1
            if nums[mid] > nums[hi]:
                if nums[lo] <= target <= nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return firstRes


if __name__ == '__main__':
    assert Solution().search([3, 1, 1], 3) == 0
    assert Solution().search([3, 1], 1) == 1
    assert Solution().search([4, 4], 4) == 0
    assert Solution().search([1, 3, 1, 1], 3) == 1
    assert Solution().search([1, 3, 1, 1], 1) == 0
    assert Solution().search([2, 2, 3, 1, 1], 2) == 0
    assert Solution().search([1, 1, 1, 3, 1, 1], 3) == 3
    assert Solution().search([3, 3, 3, 3, 1, 3], 1) == 4
    assert Solution().search([3, 3, 3, 3, 1, 3], 3) == 0
```

```python
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        i = 0
        j = len(nums)-1
        while i <= j:
            mid = i + (j-i)//2          
            if target == nums[mid]:
                return mid
            elif nums[mid] > nums[j]:    
                if nums[i] <= target <= nums[mid]:
                    j = mid - 1
                else:
                    i = mid + 1
            else:
                if nums[mid] < target <= nums[j]:
                    i = mid + 1
                else:
                    j = mid - 1                      
        return -1
```
