> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/binary_search/rotated-sorted-array.md).

# Rotated Sorted Array

## 三種方式

<https://blog.csdn.net/qq_25800311/article/details/82734239>

#### Template 1

* i , j = 0, n-1
* while i <= j
* No post process
* Search in a rotate sorted array

#### Template 2

* i, j = 0, n
* while i < j
* check i&#x20;
* Find min in rotate sorted array

#### Template 3

* i, j = 0, n-1
* while i+1 < j
* 2 post process

## 33 Search in Rotated Sorted Array

* 先判斷是不是regular sorted array, target & mid是否在斷層同一側

```python
def search(self, nums: List[int], target: int) -> int:
    n = len(nums)
    left, right = 0, n-1
    
    while left <= right:
        mid = (left+right)//2
        if nums[mid] == target: return mid
        elif (nums[mid] >= nums[left] and target >= nums[left]) or\
            (nums[mid] < nums[left] and target < nums[left]):
            if target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        else:
            if target > nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
    return -1
```

![](/files/-LrHBTHSZk9V551HdVu8)

## 81 Search in Rotated Sorted Array II

Same as 33, but with duplicates

* 特殊情況: \[1,1,4,1] target 4, A\[start] == A\[mid] => start++

```python
def search(self, nums: List[int], target: int) -> bool:
    n = len(nums)
    left, right = 0, n-1
    
    while left <= right:
        mid = (left+right)//2
        if nums[mid] == target: return True
        while left < mid and nums[left] == nums[mid]:
            left += 1
        if (nums[mid] >= nums[left] and target >= nums[left]) or\
            (nums[mid] < nums[left] and target < nums[left]):
            if target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        else:
            if target > nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
    return False
```

## 153 Find Minimum in Rotated Sorted Array

* min 必定從右半邊推算
* set target = array\[last\_index]

```python
def findMin(self, nums: List[int]) -> int:
    i, j = 0, len(nums)-1
    
    while i<j:
        mid = (i+j)//2
        if nums[mid] < nums[j]:
            j = mid
        else:
            i = mid+1   
    return nums[i]
```

## 154 Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., \[0,1,2,4,5,6,7] might become \[4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

```python
def findMin(self, nums: List[int]) -> int:
    i, j = 0, len(nums)-1
    
    while i<j:
        mid = (i+j)//2
        if nums[mid] < nums[j]:
            j = mid
        elif nums[mid] > nums[j]:
            i = mid+1
        else:
            j-=1   
    return nums[i]
```

## 34. Find First and Last Position of Element in Sorted Array

```python
def searchRange(self, nums: List[int], target: int) -> List[int]:
    first = self.findFirst(nums, target)
    last = self.findLast(nums, target)
    
    print(first, last)
    
    if first == len(nums) or nums[first] != target or nums[last] != target:
        return [-1, -1]
    
    return [first, last]
    
def findFirst(self, nums, target):
    l, r = 0, len(nums)
    
    while l < r:
        mid = (l+r)//2
        if nums[mid] >= target:
            r = mid
        else:
            l = mid + 1
    return l

def findLast(self, nums, target):
    l, r = 0, len(nums)
    
    while l < r:
        mid = (l+r)//2
        if nums[mid] > target:
            r = mid
        else:
            l = mid + 1
    return l - 1
```

## 162. Find Peak Element

```
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
```

```python
def findPeakElement(self, nums: List[int]) -> int:
    l, r = 0, len(nums)-1
    while l < r:
        mid = (l+r)//2
        if nums[mid] > nums[mid+1]:
            r = mid
        else:
            l = mid+1
            
    return l
```