Binary Search (3) template III 應用 – 陪你刷題

前面已經寫過兩篇 binary search 文章，分別介紹 binary search 以及它的不同 template ，建議先看過前兩篇文章，再來看這篇文章。

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

這篇文章將講解如何使用前篇文章中提到的 template 3 ，依照筆者經驗，到目前唯一碰到適合用 template 3 來解的也只有 Leetcode #34 ，這篇文章將講解如何使用前篇文章中提到的 template III ，如果搜尋區間內可能存在重複元素，適合使用 template III ，以下以 Leetcode #34 來講解。

Leetcode #34 Find First and Last Position of Element in Sorted Array

此題要找目標值在 array 中出現的第一個和最後一個 index ，將這題切成兩個小題來看，找第一個目標值出現的 index 這題和 Leetcode #278 相似，可以透過 template II 來解，同時也能夠透過 template III 來解，下面將會說明；而找最後一個 index 也能夠透過 template II 或 template III 來解，但使用 template II 的話需要做些小技巧，接下來一步一步來拆解這題。

Find First Position of Element - using template II

直接套用 template II ，當 loop invariant 為 false 並離開 while loop 後，還需要做 post-processing 確認最後一個元素是否等於目標值。

int searchFirst (vector<int>& nums, int target)
  {
      int left = 0, right = nums.size()-1;
      while (left < right)
      {
          int mid = left + ((right-left)>>1);
          if (nums[mid] >= target)
          {
              right = mid;
          }
          else
          {
              left = mid+1;
          }
      }
      if (nums[left] == target)
      {
          return left;
      }
      else
          return -1;
  }

Find First Position of Element - using template III

Step 1 定義初始搜尋範圍

答案可能的範圍為 index 範圍，故設 left 為 0 而 right 為 nums.size()-1 。

Step 2 Loop invariant

Template III 的 loop invariant 為 while (left+1 < right) ，loop invariant 為 false 時，此時 left+1 == right ，搜尋區間內還剩下兩個元素，需要再對這兩元素做處理，這也代表在做 binary search 期間，搜尋區間內至少包含三個以上元素，這也是使用此 template 很重要的原因，這樣找到 mid 之後，可以保證 mid 的前後都有元素，可以對前後元素做處理，後面你將會看到這個特性的重要性。

Step 3 區間縮減策略

找到 mid 後， nums[mid] 和目標值有三種關係:

1. nums[mid] == target : 代表第一個出現的 index 必定出現在 mid 或是比其小的 index ，搜尋區間右半邊可以丟掉: right = mid。
2. nums[mid] > target : 代表目標值必定在搜尋區間的左半邊，搜尋區間右半邊可以丟掉: right = mid。
3. nums[mid] < target : 代表目標值必定在搜尋區間的右半邊，搜尋區間左半邊可以丟掉: left = mid。

依照 template III 所給的模板，程式碼會如下:

  int searchFirst (vector<int>& nums, int target)
  {
      int left = 0, right = nums.size()-1;
      while (left+1 < right)
      {
          int mid = left + ((right-left)>>1);
          if (nums[mid] == target)
              right = mid;
          else if (nums[mid] > target)
              right = mid;
          else
              left = mid;
      }
  }

其實還可以針對 Template III 進行修改，會更能發揮 loop invariant 的特性，還記得使用此 loop invariant ，可以保證搜尋區間內至少包含三個以上元素，如果 nums[mid] == target ，可以再進一步檢查 mid 左邊元素，如果左邊元素不等於目標值，就等於找到目標值第一個出現的 index ，若左邊元素等於目標值，那麼代表 mid 我們不再需要，因為答案必定是 mid 左邊元素與其左邊元素，可以將搜尋區間移動到 mid 的左邊 : left = mid-1。

不論 nums[mid] 大於或小於 target ，均能將 mid 這個元素由搜尋區間剔除，綜合以上所述，binary search 可以改寫為以下程式碼:

int searchFirst (vector<int>& nums, int target)
{
    int left = 0, right = nums.size()-1;
    while (left+1 < right)
    {
        int mid = left + ((right-left)>>1);
        if (nums[mid] > target)
            right = mid-1;
        else if (nums[mid] == target)
        {
            if (mid==0 || nums[mid-1] != target)
            {
                return mid;
            }
            else
            {
                right = mid-1;
            }
        }
        else
            left = mid+1;
    }
}

由以上可知， template 只是幫助你解題，絕對不要硬生生地使用，深刻了解 binary search 的本質，包含 loop invariant 以及縮減策略的原因，才不會在解題過程中腦筋一片混亂。

Step 4 Post-processing

loop invariant 為 false 時， binary search 的 while loop 結束，此時搜尋區間只剩下兩個元素，如果要找第一個出現的 index ，會先檢查區間的第一個元素是否為目標值，若不是在檢查區間的第二個元素。

  if (nums[left] == target)
  {
      return left;
  }
  else if (nums[right] == target)
  {
      return right;
  }
  else
      return -1;

Find Last Position of Element - using template II

透過 template II 來找最後一個 index ，會進入無窮迴圈，換個角度想，可以透過找目標值加一的第一個出現位置，經由 binary search 收斂出 index 後，再檢查該 index 和其左手邊的 index 即可，可見以下程式碼:

int searchLast (vector<int>& nums, int target)
{
    int left = 0, right = nums.size()-1;
    while (left < right)
    {
        int mid = left + ((right-left)>>1);
        if (nums[mid] >= target)
        {
            right = mid;
        }
        else
        {
            left = mid+1;
        }
    }
    if (left == nums.size()-1 && nums[left] == target-1)
    {
        return left;
    }
    else if (nums[left-1] == target-1)
    {
        return left-1;
    }
    else
    {
        return -1;
    }
}

Find Last Position of Element - using template III

如同在 Find First Position of Element - using template III 章節所提到的，依照相同邏輯使用 template III 即可。

必須小心以下 edge case :

nums = []

nums = [1], target = 1

nums = [2, 2], target = 2

延伸閱讀

1. Binary Search (4) 進階問題 – 陪你刷題

Reference

• Binary Search Template Analysis

Updated on 2022-04-05 20:29:05 星期二