# **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://www.youtube.com/watch?v=lXVy6YWFcRM
Provided by. NeetCode
###### tags: `binary search` `leetcode` `medium` `值得再想`
Sign in with Wallet
Connect another wallet