---
# System prepended metadata

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

---

# **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
![image](https://hackmd.io/_uploads/rkhzwwJIa.png)
```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` `值得再想`