# **Leetcode筆記(Search in Rotated Sorted Array)**
:::info
:information_source: 題目 : Search in Rotated Sorted Array, 類型 : binary search , 等級 : medium
日期 : 2023/02/19，2023/05/14，2023/06/30，2023/10/08，2023/12/7
:::
### 嘗試
知道要用binary search，但不知道要怎樣去比
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] >= nums[l]:
if(nums[mid] == target): # 基本上這樣不符合BS原則 不會這樣檢查
break
l = mid + 1
else:
if(nums[mid] == target):
break
r = mid
return mid
```
2023/05/14，分兩邊思考，記得要考慮到target = nums[left]的情況
然後依照情況看是要跟左邊比還是右邊比
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 2345601
if nums[left] <= nums[mid]:
# 注意是跟left比
# 01
if target < nums[left]:
left = mid + 1
# 6
elif target > nums[left] and target > nums[mid]:
left = mid + 1
# 234
elif target >= nums[left] and target < nums[mid]:
right = mid - 1
# 5601234
else:
# 注意是跟right比
# 56
if target > nums[right]:
right = mid - 1
# 0
elif target < nums[right] and target < nums[mid]:
right = mid - 1
# 234
elif target <= nums[right] and target > nums[mid]:
left = mid + 1
return -1
```
2023/06/30
先處理變異區，步步逼近到mid的位置就是target，先進行大分區，舉例區說明
當mid > l -> 2345601 -> 先處理最奇怪的區域(234)，要小於mid大於l，剩下照常理分區(一個條件即可)
當mid < l -> 5601234 -> 先處理最奇怪的區域(234)，要大於mid小於r，剩下照常理分區(一個條件即可)
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
# 2345601
if nums[mid] >= nums[l]:
if target >= nums[l] and nums[mid] > target: # 3(要有等號)
r = mid - 1
elif target < nums[l]: # 0
l = mid + 1
elif nums[mid] < target: # 6
l = mid + 1
# 5601234
else:
if target <= nums[r] and target > nums[mid]: # 3(要有等號)
l = mid + 1
elif target < nums[mid]: # 0
r = mid - 1
elif target > nums[r]: # 6
r = mid - 1
return -1
```
2023/12/7
```python
"""
[0,1,2,4,5,6,7]
[4,5,6,7,0,1,2]
[6,7,0,1,2,4,5]
target = 5
mid = 3
if nums[mid] > target and nums[r] < target:
r = mid - 1
elif nums[mid] > target and nums[l] > target:
l = mid + 1
elif nums[mid] < target and nums[r] < target:
r = mid - 1
elif nums[mid] < target and nums[l] > target:
l = mid + 1
"""
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
# if left half sorted
# 2345601
# for a sorted array, they will always
# go in this section
if nums[l] <= nums[mid]:
# for sure the ans on the left
if nums[l] <= target < nums[mid]:
r = mid - 1
elif nums[mid] < target:
l = mid + 1
elif target < nums[l]:
l = mid + 1
# if right half sorted
# 5601234
else: # nums[l] > nums[mid]
if nums[mid] < target <= nums[r]:
l = mid + 1
elif target < nums[mid]:
r = mid - 1
elif nums[r] < target:
r = mid - 1
return -1
```
---
### **優化**
重點就是一樣要分成兩半去想，每一半有三種條件:
**mid > left** ex.[2,3,4,**5**,6,7,0,1] (sort left)
1. targe < left -> 往mid右半找(01)
2. target >= left 且 target < mid -> 往mid左半找(234)
3. target > left 且 target > mid -> 往mid右半找(67)
**mid < left** ex.[6,7,0,**1**,2,3,4,5] (sort right)
1. targe > right -> 往mid左半找(67)
2. target <= right 且 target > mid -> 往mid右半找(2345)
3. target < right 且 target < mid -> 往mid左半找(01)
時間複雜度O(log n)
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r: # 為防止[-2]
mid = (l + r) // 2
if nums[mid] == target: # 最後一輪必停在這
return mid
if nums[mid] >= nums[l]: # sort left
if target < nums[l] or target > nums[mid]: # 左
l = mid + 1
else:
r = mid
else: # sort right
if target > nums[r] or target < nums[mid]: # 右
r = mid
else:
l = mid + 1
return -1 # 沒其他retun(即沒找到target)
```
---
**:warning: 錯誤語法**
:::warning
:::
**:thumbsup:學習**
:::success
rotated sorted array為類似[4,5,6,7,0,1,2]，可以在兩個pivot(如7和0)分成兩半，這兩半都已經被完整sorted
while外面return -1，等於跑一跑如果沒任何東西return就return -1(同時也代表while裡面要有東西return)
:::
**思路**
**講解連結**
https://www.youtube.com/watch?v=U8XENwh8Oy8
Provided by. NeetCode
###### tags: `binary search` `leetcode` `medium` `值得再想`
Sign in with Wallet
Connect another wallet