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

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

這篇文章將講解如何使用前篇文章中提到的 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

Updated on 2021-07-03 18:36:06 星期六