Binary Search (2) Template Overview – 陪你刷題

在前一篇 binary search (1) - 陪你刷題文章中，探討一個基本的 binary search 框架，並指出 binary search 比較常用來解變形題，在 Leetcode 網站上整理出三種 binary search template ，前篇文章中針對 Leetcode #35 的解法即採取下圖中的 Template#2 ，我個人認為 Leetcode 上整理寫的較難理解，千萬不要硬背這三種 template ，應該針對題目要求做對應步驟，在本篇後面就會以實際題目演練如何應用 template 。

Binary Search Template 1

適合用在 input 一定包含 target 且 target 只存在一個的題目。
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 過程中，區間內至少會有 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;

適用題目： leetcode #162, #278

Binary Search Template 3

while 迴圈結束後會收斂得到兩個元素 ( left 和 right )，代表搜尋區間至少包含 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 的輸入卻是一個順序遞增遞減交互的陣列，又因為題目要找的是 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

Binary Search Template Analysis - Leetcode

Updated on 2021-11-14 22:58:00 星期日