在前一篇 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 星期四