在前一篇 binary search (1) - 陪你刷題文章中,探討一個基本的 binary search 框架,並指出 binary search 比較常用來解變形題,在 Leetcode 網站上整理出三種 binary search template ,前篇文章中針對 Leetcode #35 的解法即採取下圖中的 Template#2 ,我個人認為 Leetcode 上整理寫的較難理解,千萬不要硬背這三種 template ,應該針對題目要求做對應步驟,在本篇後面就會以實際題目演練如何應用 template 。
Binary Search Template 1
適合用來找特定目標。while 迴圈結束後並不會收斂出任何元素。
Distinguishing Syntax:
- Initial Condition:
left = 0, right = length-1
- Termination:
left > right
- Searching Left:
right = mid-1
- Searching Right:
left = mid+1
- 搜尋區間: 左閉右閉
Binary Search Template 2
while 迴圈結束最後會收斂得到一個元素(代表 binary search 過程中,區間內至少會有兩個元素),你必須再處理剩下的一個元素。
Distinguishing Syntax:
- Initial Condition:
left = 0, right = length
- Termination:
left == right
- Searching Left:
right = mid
- Searching Right:
left = mid+1
- 搜尋區間:左閉右開 (視答案範圍決定)
- 這個 case 最後會變成 [left, left) ,其實區間內並沒有元素,這樣的 case 並不需要對元素進行 post-processing ,反倒是下面的第2種狀況需要。
Distinguishing Syntax II:
-
Initial Condition:
left = 0, right = length-1
-
Termination:
left == right
-
Searching Left:
right = mid
-
Searching Right:
left = mid+1
-
搜尋區間:左閉右閉
-
Post-processing
// Post-processing: // End Condition: left == right if (left != nums.size() && nums[left] == target) return left; return -1;
Binary Search Template 3
while 迴圈結束後會收斂得到兩個元素 ( left
和 right
),還需要檢查 left 和 right 兩個元素。若是搜尋範圍內會出現重複的值,適合使用此模板。
Distinguishing Syntax:
-
Initial Condition:
left = 0, right = length-1
-
Termination:
left + 1 == right
-
Searching Left:
right = mid
-
Searching Right:
left = mid
-
搜尋區間:左閉右閉
-
適用題目:Leetcode #34
以下再以 Leetcode #162 Find Peak Element 為例,講解如何應用 binary search template II 。
Leetcode #162 Find Peak Element
從陣列中找出區段的最大值並回傳其 index ,區段最大值必定是比其右邊元素還要大。
nums = [1,2,1,3,5,6,4]
Answer: 元素 2 跟 6 都是 peak element ,答案可以為 index 1 或 5
以下一步一步拆解如何決定使用 template II :
Step 1 定義初始搜尋區間
首先定義初始搜尋區間,依照答案可能的範圍來定義,這題可能的答案為 index 0 到 input 大小減一,因此設定 left = 0
而 right = nums.size() - 1
,確認搜尋區間為左閉右閉。
Step 2 loop invariant
這題需要比較當前元素與其下一個相鄰元素來確認是否為 peak element ,也等同於要求搜尋區間內至少要有 2 個元素,所以 loop invariant 必須寫為 left < right
,代表 loop 終止條件為 left == right
,這個狀況下區間內僅剩一個元素,無法跟下一個相鄰元素比較,代表無法再做 binary search 。
對照到 Binary Search 的分類, 即為 Template 2 。
這題也說明了為什麼 Binary Search Template II - Leetcode Explore 這篇文章,針對 template II 的 attribute 要說 "Search Condition needs to access element's immediate right neighbor"
Step 3 區間縮減
計算出 mid 之後,需要比較其跟右邊元素的大小關係, peak 元素一定比其右邊元素大,找到符合條件元素後,該元素的右邊元素不再需要關心,因此執行 right = mid
,特別注意 mid 的前一個相鄰元素可能比前者大,代表前者並不一定是 peak element ,因此將他保留在搜尋區間內,待之後 binary search 再做比較,而不是直接回傳 mid 。
反之,若該元素比右邊元素小,那該元素絕對不是 peak ,毫不猶豫的將他剔出搜尋區間,執行 left = mid+1
。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size()-1;
while (left < right)
{
int mid = left + ((right-left)>>1);
if (nums[mid] < nums[mid+1])
left = mid +1;
else
{
right = mid;
}
}
return left;
}
};
Reference
Updated on 2021-02-11 11:04:57 星期四