二分搜 - HackMD

<style> .font{ font-family:"DFKai-sb",Garamond, serif; padding: 10px; font-size : 115%; line-height: 2; } .titles{ font-family:"DFKai-sb",Garamond, serif; padding: 20px; font-size : 150%; line-height: 2; } .small_title{ font-family:"DFKai-sb",Garamond, serif; padding: 15px; font-size : 130%; line-height: 2; } </style> <font class = "font">二分搜的應用相當廣泛，基本上題目中只要牽扯到搜尋，都可以用二分搜試試看。</font> ## 基本型態    <font class = "font">二分搜有三種基本型態：**一般的二分搜**、**左側邊界的二分搜**和**右側邊界的二分搜**，大部分題目應用都是這三種型態的變體。    二分搜的基本條件是**陣列必須經過排序**，否則無法發揮效果。以下說明三種二分搜的實作與細節。 #### <font class = "small_title">1. 一般的二分搜 </font> 這類二分搜對應到 C++ 的函式中的 **binary_search()**，單純的搜尋目標並回傳。</font> ### [704. Binary Search](https://leetcode.com/problems/binary-search/) :::spoiler <b>Code</b> ```C++= class Solution { public: int search(vector<int>& nums, int target) { int left=0; int right=nums.size()-1; // 左閉右開的區間， right 初始化須減一 while(right>=left){ // Point 1 int mid=(right+left)/2; // Point 2 if (target>nums[mid]) left=mid+1; // Point 3 else if (target < nums[mid]) right=mid-1; else if (target==nums[mid]) return mid; } return -1; } }; ``` ::: 程式中註解的 $Point$ 說明： * <font class = "font">Point 1：</font>   <font class = "font">一般寫二分搜時會有兩種寫法：<strong>while ( right > left ) </strong> 或是 <strong>while ( right >= left)</strong> ，此兩者的差異在於<b>搜尋區間的不同</b>：一個是<b><font color = "43BAF1">左閉右開</font></b>另一個是<b><font color = "43BAF1">左右皆為閉區間</font></b>而這個細節將會影響區間的縮限方式</font> * <font class = "font">Point 2：</font>   <font class = "font"> 其實還有另一種寫法： mid = left + (right - left)/2。這種寫法主要是避免整數溢位的問題</font> * <font class = "font">Point 3：</font>   <font class = "font"> 承 Point 1，由於這裡我採用<b><font color = "43BAF1">左右皆為閉區間</font></b>的寫法，當我要縮限邊界時，要寫成 right = mid - 1 或是 left = mid + 1。這樣才會是正確的區間搜尋，否則容易陷入無窮迴圈。</font> --- #### <font class = "small_title">2.邊界的二分搜</font> <font class = "font">一般的二分搜的缺點在於難以搜尋邊界，舉例：</font> > <font class = "font">a = [1,2,3,3,3,3,3]，target = 3 > 一般的二分搜找到就會馬上回傳，所以在這裡他會回傳<b>索引 3</b>，而非邊界的 <b>2 or 6</b></font> <font class = "font">有鑑於此，邊界搜尋的二分搜就此誕生。有分為左側邊界和右側邊界，分別對應到 C++ 標準函式中的 <b>lower_bound()</b> 和 <b>upper_bound()</b>。</font> <font class = "small_title">範例：</font> <font class = "font"> [34. Find First and Last Position of Element in Sorted Array ](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)</font> #### <font class = "font">1.尋找左側邊界</font> :::spoiler Code ```C++= int lower_bounds(vector<int> &nums, int &target){ int left = 0, right = nums.size()-1; int mid; while (left<= right){ mid = left + (right-left)/2; if (nums[mid] == target) { right = mid -1; } else if (nums[mid] < target) left = mid+1; else if (nums[mid] > target) right = mid -1; } if (left>=nums.size() || nums[left] != target) return -1; return left; } ``` ::: <font class = "font">這裡我的 code 一般的二分搜唯一的差別在於：</font> ```Python if (nums[mid] == target) { right = mid -1; } ``` <font class = "font">找到目標時不直接回傳，而是繼續往左側逼近，這樣最後回傳的索引值將會是最左邊的目標。</font> #### <font class = "font">2.尋找右側邊界</font> :::spoiler Code ```C++= int upper_bounds(vector<int> &nums, int &target){ int left = 0, right = nums.size()-1; int mid; while (left<=right){ mid = left+ (right-left)/2; if (nums[mid]==target){ left = mid + 1; } else if (nums[mid]<target) left = mid+1; else if (nums[mid] > target) right = mid-1; } if(right<0 || nums[right]!=target) return -1; return right; } ``` ::: <font class = "font">和左側邊界的概念差不多，但是往右側逼近。</font> --- ## <font class = "font">習題：</font> #### <font class = "font"> 1. Search a 2D Matrix I & II</font> * <font class = "font">第一題設定是每一列的第一個元素會比上一列的最後一個元素大，因此可以用一般的二分搜概念下去實作，在尋找元素時將模式轉成二維陣列即可。</font> * <font class = "font">第二題則只保證每一行和每一列是排序過的，因此如果想套二分搜，就需要每一行 ( 或列 ) 都搜尋一次才行。</font> <font class = "small_title"> 筆記區： </font> >https://hackmd.io/@rickrool/SkMqhlrzn https://hackmd.io/@rickrool/ryF6MtKXn --- #### <font class = "font">2. Search in Rotated Sorted Array </font> <font class = "font">這題很有趣，是將陣列排序後任意翻轉，並要求用二分搜解題。</font> <font class = "small_title"> 筆記區： </font> >https://hackmd.io/@rickrool/HJeXnOFm3 --- #### <font class = "font">3.圓環出口 </font> <font class = "font">這題我認為難度適中且漂亮的結合 **前綴和和二分搜**。</font> <font class = "small_title"> 筆記區： </font> >https://hackmd.io/@rickrool/rkybdFUB3 --- #### <font class = "font">4. Koko Eating Bananas </font> <font class = "font">這題則是很好的 **左側邊界搜尋的應用**</font> <font class = "small_title"> 筆記區： </font> >https://hackmd.io/@rickrool/S1xW4StLH3