---
# System prepended metadata

title: 二分搜
tags: [Note]

---

<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>
## 基本型態
&nbsp;&nbsp; <font class = "font">二分搜有三種基本型態：**一般的二分搜**、**左側邊界的二分搜**和**右側邊界的二分搜**，大部分題目應用都是這三種型態的變體。
    &nbsp;&nbsp; 二分搜的基本條件是**陣列必須經過排序**，否則無法發揮效果。以下說明三種二分搜的實作與細節。

#### <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> 
&nbsp;&nbsp;<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> 
&nbsp;&nbsp;<font class = "font"> 其實還有另一種寫法： mid = left + (right - left)/2。這種寫法主要是避免整數溢位的問題</font>
* <font class = "font">Point 3：</font> 
&nbsp;&nbsp;<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




