➣ Reading Time: 17 minutes題目出處
33. Search in Rotated Sorted Array
難度
Medium
題目分類
Array, BinarySearch
難度
medium
個人範例程式碼 – 2022/6/7 三刷
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)

input handling
處理沒有輸入的時候,return -1
Boundary conditions
binary search 的結束條件
個人範例程式碼 – 2022/4/5 二刷
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 的各種細節幾乎都已經非常清楚才寫得出來。

注意幾個討論的重點,我們可以把整個題目拆成 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/7/7 一刷
示意圖
注意事項
注意 corner case 的處理
範例: [5, 1, 3]
需要注意判斷非 ascending 時,是否該值會出現在對應的區間。
個人範例程式碼
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
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note |
---|
⭐BFS 相關題型 ⭐ |
104 | Maximum Depth of Binary Tree | BFS (分層) | | Python
| | |
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | | 內含 處理 Tree 樹問題的重點 |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | | |
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | | |
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | | |
133 | Clone Graph | BFS (分層) | Graph | Python | | Graph 的基本操作 #重要題型 |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | | |
[Lint] 127 | Topological Sorting | BFS (拓撲) | | Python
| | 內有 indegree, outdegree 介紹 #重要題型 |
207 | Course Schedule | BFS (拓樸) | Graph | Python | | |
210 | Course Schedule II | BFS (拓樸) | Graph | Python | | |
[Lint] 892 | Alien Dictionary | BFS (拓樸) | Graph | Python | | |
[Lint] 431 | Connected Component in Undirected Graph | BFS (連通塊) | Graph | Python | | 內含 BFS 模板 #重要題型 |
1091 | Shortest Path in Binary Matrix | BFS (最短路徑) | Matrix | Python
| | |
⭐ Binary Serach 相關題型 ⭐ |
33 | Search in Rotated Sorted Array | Binary Serach | Array | Python | | #重要題型 |
34 | Find First and Last Position of Element in Sorted Array | Binary Serach | | Python | | |
50 | Pow(x, n) | Binary Serach | | Python | | |
153 | Find Minimum in Rotated Sorted Array | Binary Serach | Array | Python | | |
162 | Find Peak Element | Binary Serach | | Python | | |
278 | First Bad Version | Binary Serach | | Python | | |
658 | Find K Closest Elements | Binary Serach | | Python | | |
704 | Binary Search | Binary Serach | | Python | | |
852 | Peak Index in a Mountain Array | Binary Serach | | Python
| | |
[Lint] 14 | First Position of Target | Binary Serach | | Python
| | |
[Lint] 140 | Fast Power | Binary Serach | | Python | | |
[Lint] 447 | Search in a Big Sorted Array | Binary Serach | Array | Python | | |
[Lint] 458 | Last Position of Target | Binary Serach | | Python | | |
191 | Number of 1 Bits | Bit Manipulation | | Python
| | |
⭐ Data Stream 相關題型 ⭐ |
[Lint] 642 | Moving Average from Data Stream | Data Stream | Queue | Python
| | |
⭐ Design 相關題型 ⭐ |
155 | Min Stack | Design | | Python
| | |
[Lint] 659 | Encode and Decode Strings | Design | | Python
| | |
232 | Implement Queue using Stacks | Design | Queue, Stack | Python
| | |
⭐ DFS 相關題型 ⭐ |
98 | Validate Binary Search Tree | DFS | | Python
| | |
2265 | Count Nodes Equal to Average of Subtree | DFS | | Python
| | 292nd Weekly Contest |
2261 | K Divisible Elements Subarrays | DFS | | Python
| | 內含 python substring 常見作法 / 291st LeetCode Weekly Contest |
22 | Generate Parentheses | DFS | | Python
| | |
79 | Word Search | DFS | Matrix | Python
| | |
126 | Word Ladder II | DFS | | Python
| | |
212 | Word Search II | DFS | Tree | Python
| | |
290 | Word Pattern | DFS | | Python
| | |
[Lint] 829 | Word Pattern II | DFS | | Python
| | |
31 | Next Permutation | DFS (排列) | | Python
| | |
46 | Permutations | DFS (排列) | | Python
| | #重要題型 |
47 | Permutations II | DFS (排列) | | Python
| | #重要題型 |
51 | N-Queens | DFS (排列) | | Python
| | |
52 | N-Queens II | DFS (排列) | | Python
| | |
[Lint] 862 | Next Closest Time | DFS (排列) | | Python
| | 內有 set 判斷是否 subset 的用法 |
10 | Regular Expression Matching | DFS (組合) | | Python
| | |
77 | Combinations | DFS (組合) | | Python
| | #重要題型 |
39 | Combination Sum | DFS (組合) | | Python
| | |
40 | Combination Sum II | DFS (組合) | | Python
| | |
216 | Combination Sum III | DFS (組合) | | Python
| | |
377 | Combination Sum IV | DFS (組合) | | Python
| | |
44 | Wildcard Matching | DFS (組合) | | Python
| | |
78 | Subsets | DFS (組合) | | Python
| | #重要題型 |
90 | Subsets II | DFS (組合) | | Python
| | #重要題型 |
131 | Palindrome Partitioning | DFS (組合) | | Python
| | |
139 | Word Break | DFS (組合) | | Python
| | |
140 | Word Break II | DFS (組合) | | Python
| | |
[Lint] 90 | k Sum II | DFS (組合) | | Python
| | |
[Lint] 680 | Split String | DFS (組合) | | Python
| | |
173 | Binary Search Tree Iterator | DFS (BST) | BST | Python
| | #重要題型 |
230 | Kth Smallest Element in a BST | DFS (BST) | BST | Python
| | |
[Lint] 448 | Inorder Successor in BST | DFS (BST) | BST | Python
| | |
[Lint] 900 | Closest Binary Search Tree Value | DFS (BST) | BST | Python
| | |
[Lint] 901 | Closest Binary Search Tree Value II | DFS (BST) | BST | Python
| | #綜合難題 |
208 | Implement Trie (Prefix Tree) | DFS (Graph) | Tree | Python
| | |
17 | Letter Combinations of a Phone Number | DFS (Graph) | Graph | Python
| | |
332 | Reconstruct Itinerary | DFS (Graph) | Graph | Python
| | #重要題型 |
110 | Balanced Binary Tree | DFS (Tree) | Tree | Python
| | |
226 | Invert Binary Tree | DFS (Tree) | Tree | Python
| | |
572 | Subtree of Another Tree | DFS (Tree) | Tree | Python
| | |
105 | Construct Binary Tree from Preorder and Inorder Traversal | DFS (Tree) | Tree | Python
| | |
112 | Path Sum | DFS (Tree) | | Python
| | |
113 | Path Sum II | DFS (Tree) | Tree | Python
| | |
235 | Lowest Common Ancestor of a Binary Search Tree | DFS (Tree) | Tree | Python
| | |
236 | Lowest Common Ancestor of a Binary Tree | DFS (Tree) | Tree | Python
| | #重要題型 |
257 | Binary Tree Paths | DFS (Tree) | Tree | Python
| | |
[Lint] 474 | Lowest Common Ancestor II | DFS (Tree) | Tree | Python
| | |
[Lint] 578 | Lowest Common Ancestor III | DFS (Tree) | Tree | Python
| | |
[Lint] 596 | Minimum Subtree | DFS (Tree) | Tree | Python
| | |
543 | Diameter of Binary Tree | DFS (Tree) | | Python
| | |
144 | Binary Tree Preorder Traversal | DFS (Tree) | Tree | Python
| | 內含 處理 Tree 樹問題的重點 |
145 | Binary Tree Postorder Traversal | DFS (Tree) | Tree | Python
| | |
114 | Flatten Binary Tree to Linked List | DFS (Tree) | Tree | Python
| | |
⭐ Dynamic Programming 相關題型 ⭐ |
338 | Counting Bits | DP | | Python
| | |
309 | Best Time to Buy and Sell Stock with Cooldown | DP | | Python
| | |
2266 | Count Number of Texts | DP | | Python
| | 292nd Weekly Contest |
2262 | Total Appeal of A String | DP | | Python
| | 291st Weekly Contest |
91 | Decode Ways | DP | | Python | C++ | |
70 | Climbing Stairs | DP | | Python | C++ | |
221 | Maximal Square | DP | | Python
| | |
53 | Maximum Subarray | DP (一維) | Array | Python | C++ | 內含 C++ vector max 用法整理 |
91 | Decode Ways | DP (一維) | | Python
| | |
55 | Jump Game | DP (一維) | | Python
| | #重要題型 |
45 | Jump Game II | DP (一維) | | Python
| | #重要題型 |
198 | House Robber | DP (一維) | | Python
| | |
213 | House Robber II | DP (一維) | | Python
| | |
509 | Fibonacci Number | DP (一維) | | Python
| | |
122 | Best Time to Buy and Sell Stock II | DP (一維) | | Python
| | |
300 | Longest Increasing Subsequence | DP (一維接龍, LIS) | | Python
| | #重要題型 |
62 | Unique Paths | DP (二維) | | Python | C++ | |
63 | Unique Paths II | DP (二維) | | Python | C++ | |
152 | Maximum Product Subarray | DP (二維) | | Python
| | #重要題型 |
118 | Pascal’s Triangle | DP (二維) | | Python
| | 內含 python sum of two list (list add 相加方法整理) |
322 | Coin Change | DP (背包問題) | | Python
| | 內含 DP 背包問題模板 #重要題型 |
518 | Coin Change 2 | DP (背包問題) | | Python
| | #重要題型 |
[Lint] 92 | Backpack | DP (背包問題) | | Python
| | |
[Lint] 125 | Backpack II | DP (背包問題) | | Python
| | |
[Lint] 440 | Backpack III | DP (背包問題) | | Python
| | |
[Lint] 562 | Backpack IV | DP (背包問題) | | Python
| | |
[Lint] 563 | Backpack V | DP (背包問題) | | Python
| | |
[Lint] 798 | Backpack VII | DP (背包問題) | | Python
| | |
[Lint] 799 | Backpack VIII | DP (背包問題) | | Python
| | |
[Lint] 800 | Backpack IX | DP (背包問題) | | Python
| | |
[Lint] 801 | Backpack X | DP (背包問題) | | Python
| | |
1143 | Longest Common Subsequence | DP (LCS) | | Python
| | |
494 | Target Sum | DP (Memoization) | | Python
| | |
2267 | Check if There Is a Valid Parentheses String Path | DP (Memoization) | | Python
| | 內含:Memoization 記憶化搜索筆記 / 292nd Weekly Contest |
⭐ Hash 相關題型 ⭐ |
13 | Roman to Integer | Hash | | Python
| | |
73 | Set Matrix Zeroes | Hash | | Python | C++ | 內含 python while-else 用法說明 |
692 | Top K Frequent Words | Hash | | Python
| | 內含 python 自定義排序 key function 的使用方法 |
846 | Hand of Straights | Hash | | Python
| | |
347 | Top K Frequent Elements | Hash | | Python
| | |
205 | Isomorphic Strings | Hash | | Python
| | |
268 | Missing Number | Hash | | Python
| | |
242 | Valid Anagram | Hash | | Python
| | |
763 | Partition Labels | Hash | Interval | Python
| | |
383 | Ransom Note | Hash | | Python
| | |
387 | First Unique Character in a String | Hash | | Python
| | |
2186 | Minimum Number of Steps to Make Two Strings Anagram II | Hash | | Python
| | 282nd Weekly Contest |
[Lint] 793 | Intersection of Arrays | Hash | | Python
| | |
146 | LRU Cache | Hash | | Python
| | |
387 | First Unique Character in a String | Hash | | Python
| | |
[Lint] 920 | Meeting Rooms | Hash | Interval | Python
| | #重要題型 |
[Lint] 920 | Meeting Rooms | Hash | Interval | Python
| | #重要題型 |
[Lint] 919 | Meeting Rooms II | Hash | Interval | Python
| | #重要題型 |
[Lint] 919 | Meeting Rooms II | Hash | Interval | Python
| | #重要題型 |
349 | Intersection of Two Arrays | Hash | | Python
| | |
217 | Contains Duplicate | Hash | Array | Python
| C++ | 內含 C++ set, unordered_set 用法整理 |
137 | Single Number II | Hash | | Python
| | |
350 | Intersection of Two Arrays II | Hash | | Python
| | |
2248 | Intersection of Multiple Arrays | Hash | | Python
| | 290th Weekly Contest |
49 | Group Anagrams | Hash (Anagrams) | | Python
| | |
217 | Contains Duplicate | Hash (Duplicate) | | Python
| | |
128 | Longest Consecutive Sequence | Hash (LCS) | | Python
| | |
136 | Single Number | Hash, Bit Manipulation | | Python
| | |
⭐ Heap 相關題型 ⭐ |
264 | Ugly Number II | Heap | | Python
| | |
⭐ Stack 相關題型 ⭐ |
739 | Daily Temperatures | Stack | | Python
| | |
496 | Next Greater Element I | Stack | | Python
| | |
503 | Next Greater Element II | Stack | | Python
| | |
20 | Valid Parentheses | Stack (Parentheses) | | Python
| | 內含用 python List 組出 Stack, Queue 的方法整理 |
⭐ Two pointers 相關題型 ⭐ |
11 | Container With Most Water | Two pointers | | Python
| | |
42 | Trapping Rain Water | Two pointers | | Python
| | |
74 | Search a 2D Matrix | Two pointers | Matrix | Python
| | |
141 | Linked List Cycle | Two pointers | Linked List | Python
| | |
142 | Linked List Cycle II | Two pointers | Linked List | Python
| | 內含 python while-else 用法介紹 |
283 | Move Zeroes | Two pointers | | Python | | |
876 | Middle of the Linked List | Two pointers | | Python
| | |
2260 | Minimum Consecutive Cards to Pick Up | Two pointers (快慢) | | Python
| | 291st Weekly Contest |
21 | Merge Two Sorted Lists | Two pointers (Merge) | Linked List | Python
| | 內含 python Linked List 基本操作 (for 新手教學) |
88 | Merge Sorted Array | Two pointers (Merge) | | Python | C++ | 內含 python while-else 用法說明 |
1 | Two Sum | Two pointers (NSum) | Array | Python | C++ | 內有 Python list comprehesion / dict comprehesion 整理 / C++ map find 方法補充 (dict find) |
15 | 3Sum | Two pointers (NSum) | Array | Python | | |
16 | 3Sum Closest | Two pointers (NSum) | | Python
| | |
167 | Two Sum II – Input Array Is Sorted | Two pointers (NSum) | | Python
| | |
[Lint] 382 | Triangle Count | Two pointers (NSum) | | Python
| | |
[Lint] 533 | Two Sum – Closest to Target | Two pointers (NSum) | | Python
| | |
[Lint] 587 | Two Sum – Unique Pairs | Two pointers (NSum) | | Python | | |
5 | Longest Palindromic Substring | Two pointers (Palindrome) | | Python | C++ | 內含 C++ string.substr() 用法筆記
|
9 | Palindrome Number | Two pointers (Palindrome) | | Python | | |
125 | Valid Palindrome | Two pointers (Palindrome) | String | Python | | 內含 python isalpha(), isalnum() 的整理 |
680 | Valid Palindrome II | Two pointers (Palindrome) | | Python | | |
409 | Longest Palindrome
| Two pointers (Palindrome) | | Python | | |
647 | Palindromic Substrings | Two pointers (Palindrome) | | Python
| | |
234 | Palindrome Linked List | Two pointers (Palindrome) | Linked List | Python
| | 內含 reverse LinkedList 方法 |
75 | Sort Colors | Two pointers (partition) | | Python
| | #重要題型 |
[Lint] 5 | Kth Largest Element | Two pointers (partition) | | Python
| | #重要題型 |
[Lint] 31 | Partition Array | Two pointers (partition) | | Python
| | #重要題型 |
[Lint] 143 | Sort Colors II | Two pointers (partition) | | Python
| | #重要題型 |
[Lint] 461 | Kth Smallest Numbers in Unsorted Array | Two pointers (partition) | | Python
| | #重要題型 |
3 | Longest Substring Without Repeating Characters | Two pointers (Sliding Window) | | Python | | |
76 | Minimum Window Substring | Two pointers (Sliding Window) | | Python | | |
239 | Sliding Window Maximum | Two pointers (Sliding Window) | | Python
| | |
⭐ 其他題型 / 待分類 ⭐ |
2 | Add Two Numbers | | Linked List | Python
| | |
7 | Reverse Integer | | | Python
| | |
19 | Remove Nth Node From End of List | | Linked List | Python
| | |
36 | Valid Sudoku | | | Python
| | |
48 | Rotate Image | | Matrix | Python
| | |
621 | Task Scheduler | | | Python
| | |
202 | Happy Number | | | Python
| | |
238 | Product of Array Except Self | | | Python
| | |
222 | Count Complete Tree Nodes | | Tree | Python
| | |
674 | Longest Continuous Increasing Subsequence | | | Python
| | |
435 | Non-overlapping Intervals | | Interval | Python
| | |
88 | Merge Sorted Array | | | Python
| | 內含 python while-else 用法說明 |
2264 | Largest 3-Same-Digit Number in String | | | Python
| | 292nd Weekly Contest |
56 | Merge Intervals | | Interval | Python
| | 內含:python sorted key 搭配 lambda 的用法範例 |
57 | Insert Interval | | Interval | Python
| | |
61 | Rotate List | | Linked List | Python
| | |
2259 | Remove Digit From Number to Maximize Result | | | Python
| | 291st Weekly Contest |
53 | Maximum Subarray | | | Python
| | |
54 | Spiral Matrix | | | Python
| | |
228 | Summary Ranges | | | Python
| | |
263 | Ugly Number | | | Python
| | |
203 | Remove Linked List Elements | | Linked List | Python
| | 內含 Linked List remove 操作 part 2 (for 新手教學) |
206 | Reverse Linked List | | Linked List | Python
| | 內含 Linked List reverse 反轉操作 part 3 (for 新手教學) |
189 | Rotate Array | | Array | Python
| | |
2185 | Counting Words With a Given Prefix | | String | Python
| | 282nd Weekly Contest |
134 | Gas Station | | | Python
| | |
121 | Best Time to Buy and Sell Stock | | | Python
| | |
83 | Remove Duplicates from Sorted List | | Linked List | Python
| | |
566 | Reshape the Matrix | | Matrix | Python
| | 內含 python array 初始化, index 操作與控制範例 |
2243 | Calculate Digit Sum of a String | | | Python
| | 289th Weekly Contest |
2244 | Minimum Rounds to Complete All Tasks | | | Python
| | 289th Weekly Contest |
2249 | Count Lattice Points Inside a Circle | | | Python
| | 290th Weekly Contest |
⭐【喜歡我的文章嗎? 歡迎幫我按讚~ 讓基金會請創作者喝一杯咖啡! 】
如果喜歡我的文章,請幫我在下方【按五下Like】 (Google, Facebook 免註冊),會由 「LikeCoin」 贊助作者鼓勵繼續創作,讀者們「只需幫忙按讚,完全不用出錢」哦!
 |
---|
Post Views:
962