---
# System prepended metadata

title: '**Leetcode筆記(Find Minimum in Rotated Sorted Array)**'
tags: [值得再想, binary search, medium, leetcode]

---

# **Leetcode筆記(Find Minimum in Rotated Sorted Array)**


:::info
:information_source: 題目 : Find Minimum in Rotated Sorted Array, 類型 : binary search , 等級 : medium
日期 : 2023/02/19，2023/05/15，2023/06/30，2023/12/02，2024/04/01，2024/10/08
:::


### 嘗試

時間複雜度O(n)，沒有用到額外記憶體，但題目要求時間複雜度要O(logn)

```python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        return min(nums)
```
2023/05/15
數組分為: left…mid…right
先判斷左(left-mid)右(mid-right)邊哪段是正常的
* nums=[3,4,5,1,2]
nums[left]=3, nums[mid]=5, nums[right]=2
右邊為不正常排序，表示最小值在此段
所以left=mid+1 縮小判斷範圍
* nums=[4,5,0,1,2,3]
nums[left]=4, nums[mid]=0, nums[right]=3
左邊為不正常排序，表示最小值在此段
right=mid-1 縮小判斷範圍
```python
class Solution:
    def findMin(self, nums: List[int]) -> int:

        l, r = 0, len(nums) - 1
        res = float("inf")

        while l <= r:
            mid = (l + r) // 2
            res = min(res, nums[mid])
            # 右邊不正常
            if nums[mid] > nums[r]:
                l = mid + 1
            # 左邊不正常
            # nums[mid] < nums[l]
            else:
                r = mid - 1
        
        return res
```
2023/06/30

嘗試用另一[解法](https://blog.csdn.net/fuxuemingzhu/article/details/79533470)
如果l的數字小於r的數字 -> 符合常規的排列 -> 值回傳最小值l
如果l的數字大於r的數字 -> 不符合常規的排列，當在這個情況底下時 -> 用mid和r的大小來判斷異常區在哪(左邊還是右邊)，最後l和r兩個數會差1，並且異常值會在r上面

```python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        l, r = 0, len(nums) - 1
        # 如果初始的nums[left]小於nums[right]
        # 那必定是正序
        if nums[l] < nums[r]:
            return nums[l]

        while nums[l] > nums[r]:
            # 當兩個只有一格之差
            if l + 1 == r :
                return nums[r]
            mid = (l + r) // 2
            # nums = [3,4,5,1,2]
            if nums[mid] > nums[r]: # 異常區在右邊
                l = mid
            # nums = [5,1,2,3,4]
            elif nums[mid] < nums[r]: # 異常區在左邊
                r = mid
```
2023/12/02
```python
"""
[0,1,2,4,5,6,7]

[7,0,1,2,4,5,6]

[4,5,6,7,0,1,2]
[7,0,1,2,4,5,6]
[2,4,5,6,7,0,1]
[0,1,2,4,5,6,7]

l, r = 0, 6
mid = 3
mid > r: l = mid + 1
mid < r and mid < l : r = mid - 1
mid > r and mid > l : l = mid + 1
mid > l and mid < r : r = mid - 1

[4,5,6,7,0,1,2]
l, r = 0, 6
mid = 3

l, r = 4, 6
mid = 5
res = 1
r = 4

l, r = 4, 4
mid = 4
res = 0
r = 3
"""

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        res = float("inf")
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] > nums[r]:
                l = mid + 1
            else: # nums[mid] <= nums[r]
                res = min(res, nums[mid])
                r = mid - 1

        return res
```
2024/04/01
如果不在中間篩選mid的話，
```
[3,1,2]
l = 0, r = 2, mid = 1
```
會直接跑到3
如果r = mid，在一般case中又會形成無限迴圈(r不更動)
所以需要在r中間攔住mid去檢查
```python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        res = float("inf")
        while l <= r:
            mid = (l + r) // 2 
            if nums[r] < nums[mid]:
                l = mid + 1
            else:
                res = min(res, nums[mid])
                r = mid - 1

        return res
```

2024/10/08
```python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            mid = (l + r) // 2
            if nums[mid] < nums[r]:
                r = mid
            else:
                l = mid + 1
        
        return nums[l]
```


---
### **優化**

看到logn的時間複雜度就要想到binary search，它的精隨就是左邊小右邊大

時間複雜度O(logn)

```python
# pseudocode
if nums[m] >= nums[L]
    search Right
else 
    search Left
```

```python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        res = nums[0]
        l = 0
        r = (len(nums)-1)

        while l <= r: #  最後一次執行時會是 l = r = mid
            mid = (r + l) // 2 # 地板除法 (到最後越來越逼近 比到只剩兩組時(倒數第二次) mid和l會重疊)
            if nums[mid] >= nums[l]:
                res = min(res, nums[l]) # 考慮到最小值就在最左的case
                l = mid + 1 # 找右
            else:
                #res = min(res, nums[r]) #因為最後nums[mid] = nums[l]也不會跑進來
                r = mid # 找左  
        return res
```
---


**:warning: 錯誤語法** 
:::warning

:::


**:thumbsup:學習** 
:::success
記得必須要有一個while讓程式持續運行
這裡的mid = (left + right) // 2
:::

**思路**
![](https://i.imgur.com/4DnqG9w.png)

**講解連結**
https://www.youtube.com/watch?v=lXVy6YWFcRM
Provided by. NeetCode

###### tags: `binary search` `leetcode` `medium` `值得再想`