---
description: LeetCode 33 & 81
---

# Search in Rotated Sorted Array I & II

```python
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        low = 0
        high = len(nums)-1
        
        while low <= high:
            
            mid = (high + low) //2
                    
            if nums[mid] == target:
                return mid
            while mid < high and nums[mid] == nums[high]:
                high = high - 1
            # [1, 2, 3, |4| ..... 0]
            # [4, 4, 4, |4| ..... 0]
            if nums[mid] > nums[high]:
                #正常排序
                if nums[low] <= target <= nums[mid]:
                    high = mid -1
                else:
                    low = mid + 1
            else:
            # nums[mid]< nums[high]
            # [7 ........|3|, 4,  5, 6]
                if nums[mid] < target <= nums[high] :
                    low = mid + 1
                else:
                    high = mid - 1
            
        return -1
```

## Follow up

1. duplicates
2. return the first position of target in the array

```python
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        lo = 0
        hi = len(nums) - 1
        firstRes = -1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if target == nums[mid]:
                firstRes = mid
            # [3, 3, 3, 3, 1, 3]
            #           m
            #           h
            # l
            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
```
