在前一篇 binary search (1) - 陪你刷題文章中，探討一個基本的 binary search 框架，並指出 binary search 比較常用來解變形題，在 Leetcode 網站上整理出三種 binary search template ，前篇文章中針對 Leetcode #35 的解法即採取下圖中的 Template#2 ，我個人認為 Leetcode 上整理寫的較難理解，千萬不要硬背這三種 template ，應該針對題目要求做對應步驟，在本篇後面就會以實際題目演練如何應用 template 。
Binary Search Template 1
binary search 結束後並不會收斂出任何元素。
適合用在
- input array 一定包含 target 且 target 只存在一個。
- 希望把 array 內所有的元素都搜尋過，不會收斂出任何的元素做 post-processing。
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
binary search 結束最後會收斂得到一個元素，代表 binary search 過程中，區間內至少會有 2 個元素，搜尋結束後，你必須再處理剩下的一個元素。
Distinguishing Syntax :
- 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
binary search 結束後會，搜尋區間會剩下兩個元素，代表搜尋區間至少包含 3 個元素，搜尋結束後，還需要檢查 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
這題乍看之下，你會覺得為什麼可以用 binary search ，回想在前篇文章中，提到 bianry search 是應用在有序的陣列，但 #162 的輸入卻是一個順序遞增遞減交互的陣列(其實並不是只有在有序陣列上才能使用 binary search ，像是 LC #33, #81 和 #153 就是在非有序陣列上使用 bianry search)。
這題要找的是 peak element ，並不是單純特定目標值，可以透過 binary search 來找，是根基於以下判斷:
- 如果 nums[mid] < nums[mid+1], 代表 peak element 一定存在於右半邊 (包含 mid)。
- 如果 nums[mid] > nums[mid+1], 代表 peak element 一定存在於左半邊 (包含 mid)。
(推薦可以觀看 mit opencourse 6.006 1. Algorithmic Thinking, Peak Finding，這邊有一段即在講解此問題)
以下一步一步拆解如何決定使用 template II ：
Step 1 定義初始搜尋區間
首先定義初始搜尋區間，依照答案可能的範圍來定義，因此設定 left = 0 而 right = nums.size() - 1，確認搜尋區間為左閉右閉。
Step 2 區間縮減
計算出 mid 之後，需要比較其跟右邊元素的大小關係， peak 元素一定比其右邊元素大，若真的比右邊元素大，該元素的右手邊所有元素不再需要關心，只需要關注 data[left, ... mid] ，特別注意 mid 的前一個元素可能比 mid 大，代表 mid 並不一定是 peak element ，需要將 mid 保留在搜尋區間內，因此執行 right = mid ，待之後 binary search 再做比較，而不是直接回傳 mid 。
反之，若該元素比右邊元素小，那該元素絕對不是 peak ，毫不猶豫的將他剔出搜尋區間，執行 left = mid+1 。
Step 3 loop invariant
這題需要比較當前元素與其下一個相鄰元素來確認是否為 peak element ，也等同於要求搜尋區間內至少要有 2 個元素，所以 loop invariant 必須寫為 left < right ，代表 loop 終止條件為 left == right ，這個狀況下區間內僅剩一個元素，無法跟下一個相鄰元素比較，代表無法再做 binary search 。
這題也說明了為什麼 Binary Search Template II - Leetcode Explore 這篇文章，針對 template II 的 attribute 要說 "Search Condition needs to access element's immediate right neighbor" ，因為區間內至少會有兩個元素，且 loop invariant 為 left < right ，代表必定有一個元素與一個比他大的 right neighbor
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;
}
};Complexity
Time complexity: O (log n)
Space Complexity: O(1)
延伸閱讀
Reference
Updated on 2022-04-05 20:26:47 星期二
在〈Binary Search (2) Template Overview – 陪你刷題〉中有 2 則留言