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

適合用來找特定目標。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;
  • 適用題目: leetcode #162, #278

Binary Search Template 3

while 迴圈結束後會收斂得到兩個元素 ( leftright ),還需要檢查 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 = 0right = 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

  1. Binary Search Template Analysis - Leetcode

Updated on 2021-02-11 11:04:57 星期四