【Leetcode】python - [33] Search in Rotated Sorted Array 個人解法筆記 #重要題型

題目出處

難度

Medium

題目分類

Array, Binary Search

2026-07-23 四刷

個人範例程式碼 - 四刷 (2026/07/23)

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
            
            # seperate and find asc
            if nums[left] <= nums[mid]: # left is asc side?
                if nums[left] <= target < nums[mid]: # target in asc
                    right = mid - 1
                else:
                    left = mid + 1
            else: # right is asc side
                if nums[mid] < target <= nums[right]: # target in asc
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

算法說明

分邊, 先確認值是否在 Mid 位置
找 asc 那邊
判斷 asc 那側, target 是否在區間裡面不是就去另外一邊找
看哪邊需要 right = mid - 1, left = mid + 1

Time Complexity

O(logN)

Space Complexity

O(1)

Boundary conditions

單一元素：[5]
left <= right, at least check mid once
[1,3], target 3
left += 1, then found
[3,1], target 1
left += 1, then found
特別留意鎖定 asc 範圍時的邊界 nums[left] <= target, target <= nums[right]
另外一邊因為前面已經有比較過 target == nums[mid] 等於反而沒意義, 前面就會抓到
另外還需要留意找 asc 時, nums[left] <= nums[mid] 可包含等於, 這才能處理當 target 在另外一側時, 此等於的邏輯能成功的讓 left, right 更新正確的值

2022-06-07 三刷

個人範例程式碼 - 三刷 (2022/06/07)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums) - 1

        while start + 1 < end:
            mid = (start + end) // 2
            # print(start, mid, end)
            # print(nums[start], nums[mid], nums[end])

            if nums[mid] == target:
                return mid

            if nums[start] < nums[mid]: # front: simple go up
                if nums[start] <= target < nums[mid]:
                    end = mid   
                else:
                    start = mid
            else: # back: simple go up
                if nums[mid] < target <= nums[end]:
                    start = mid
                else:
                    end = mid

        else:
            if nums[start] == target:
                return start
            elif nums[end] == target:
                return end
            else:
                return -1

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

分成 2 種 case 討論，2 種 case 底下又有兩種 case，

先看 mid 的落點，
分成「start < mid」或「mid < end」

再來各自看 target 的落點，(看有沒有落在單純上升的範圍)。

最後我們可以整理成：

「start < mid」

「start < target < mid」：純上升範圍
「else」：亂的範圍 (依然是 rotated sorted array)

「mid < end」

「mid < target < end」：純上升範圍
「else」：亂的範圍 (依然是 rotated sorted array)

【Leetcode】python - [33] Search in Rotated Sorted Array 個人解法筆記 #重要題型

input handling

處理沒有輸入的時候，return -1

Boundary conditions

binary search 的結束條件

2022-04-05 二刷

個人範例程式碼 - 二刷 (2022/04/05)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1

        start, end = 0, len(nums)-1
        while(start + 1 < end):
            mid = (start + end) // 2
            if(nums[mid] >= nums[end]):
                if(nums[start] <= target <= nums[mid]):
                    end = mid
                else:
                    start = mid
            else: # (nums[mid] < nums[end]):
                if(nums[mid] <= target <= nums[end]):
                    start = mid
                else:
                    end = mid

        else:
            if(nums[start] == target):
                return start
            elif(nums[end] == target):
                return end
            else:
                return -1

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

這題可以說是 binary search 的最 #重要問題，
主要因為要寫得出這題，基本上要對 binary search 的各種細節幾乎都已經非常清楚才寫得出來。

【Leetcode】python - [33] Search in Rotated Sorted Array 個人解法筆記 #重要題型

注意幾個討論的重點，我們可以把整個題目拆成 2*2 個 case，

比 start 還大的情況 (等同於 >= end 的情況)
比 end 還小的情況

然後再針對這兩個情況，再拆成兩種 mid 的情況：

比 start 還大的情況 (等同於 >= end 的情況)

start < target < mid 的情況
else

比 end 還小的情況

else
mid < target < end 的情況

我們要注意移動的時候要移動 start 還是 end，可以從圖上觀察而出。

此外，邊界條件的處理也是此題相當重要的關鍵。

「>= end」

這個觀念我們在【Leetcode】python – [153] Find Minimum in Rotated Sorted Array 個人解法筆記
已經有詳細討論過，如果不清楚可以去看看

「邊界有沒有等於」?

這問題也非常重要，因為這會影響我們要移動 start 或是 end，
而我們需要讓邊界「等於」，因為如果 mid 正好是解答，

我們需要讓「移動側 = mid = target」，因此邊界條件中會有「包含等於的條件」

input handling

處理沒有輸入的時候，return -1

Boundary conditions

binary search 的結束條件

2021-07-07 一刷

個人解法筆記 (解法重點) - 2021/7/7 一刷

示意圖

注意事項

注意 corner case 的處理
範例： [5, 1, 3]

需要注意判斷非 ascending 時，是否該值會出現在對應的區間。

個人範例程式碼 - 一刷 (2021/07/07)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l_idx , r_idx = 0, len(nums)-1

        while l_idx <= r_idx:
            mid_idx = (l_idx + r_idx)//2

            if nums[mid_idx] == target:
                return mid_idx

            # search left
            if nums[l_idx] <= nums[mid_idx]:
                if nums[l_idx] <= target and target < nums[mid_idx]: # ascending side
                    r_idx = mid_idx - 1
                else:
                    l_idx = mid_idx + 1

            # search right
            else: 
                if nums[mid_idx] < target and target <= nums[r_idx]: # ascending side
                    l_idx = mid_idx + 1
                else:
                    r_idx = mid_idx - 1


        return -1