---
type: slide
---

# binary search algorithm

---

# 終極密碼

----

# 1 ~ 100猜一個數字
# 告訴你太大或太小

----

# 當然從頭開始猜啊XD

----

## 線性搜尋(linear search)：
最佳時間複雜度: O(1)
平均時間複雜度: O(n)
最差時間複雜度: O(n)

----

# 每次都選中間的

----

# 終極密碼是88

----

範圍：1~100
猜：50 -> 太小

----

範圍：51~100
猜：75 -> 太小

----

範圍：76~100
猜：88 -> 中了

----

## 二分搜尋(binary search)：
最佳時間複雜度: O(1)
平均時間複雜度: O(log n)
最差時間複雜度: O(log n)

----

迴圈版本

int password;

int find(int l, int r)
{
    int mid;
	
    while(l <= r)
    {
		mid = l + (r - l) / 2; 
		if(mid < password) l = mid+1;
		else if (mid > password) r = mid-1;
		else return mid;
	}
    return -1;
}

----

遞迴版本

int password;

int find(int l, int r)
{
    int mid =(l+r)/2;
    if(mid<password) return find(mid+1, r);
    if(mid>password) return find(l, mid-1);
    return mid;
}

---

# 尋找排序過的序列裡的某個值

----

要找10
<table>
<colgroup span="2" style="background-color: gray;"></colgroup>
<colgroup span="1" style="background-color: red;"></colgroup>
<colgroup span="4" style="background-color: gray;"></colgroup>

<tr>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
</tr>
<tr>
<td>3</td>
<td>6</td>
<td>10</td>
<td>11</td>
<td>23</td>
<td>45</td>
<td>77</td>
</tr>

</table>

----

<table>
<colgroup span="2" style="background-color: gray;"></colgroup>
<colgroup span="1" style="background-color: red;"></colgroup>
<colgroup span="4" style="background-color: black;"></colgroup>

<tr>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
</tr>
<tr>
<td>3</td>
<td>6</td>
<td>10</td>
<td>11</td>
<td>23</td>
<td>45</td>
<td>77</td>
</tr>

</table>

----

<table>
<colgroup span="2" style="background-color: black;"></colgroup>
<colgroup span="1" style="background-color: red;"></colgroup>
<colgroup span="4" style="background-color: black;"></colgroup>

<tr>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
</tr>
<tr>
<td>3</td>
<td>6</td>
<td>10</td>
<td>11</td>
<td>23</td>
<td>45</td>
<td>77</td>
</tr>

</table>

----

<table>
<colgroup span="2" style="background-color: black;"></colgroup>
<colgroup span="1" style="background-color: green;"></colgroup>
<colgroup span="4" style="background-color: black;"></colgroup>

<tr>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
</tr>
<tr>
<td>3</td>
<td>6</td>
<td>10</td>
<td>11</td>
<td>23</td>
<td>45</td>
<td>77</td>
</tr>

</table>

----

vector<int> vec = {3, 6, 10, 11, 23, 45, 77};

int binary_search(vector<int> &nums, int target)
{
    int l = 0;
    int r = nums.size() - 1; // array 長度 -1
    while (l <= r)
    {
        int mid = l + (r-l) / 2; 
        if (nums[mid] > target) r = mid - 1;
        else if (nums[mid] < target) l = mid + 1;
        else   return mid; // 剛好找到 target
    }
    return -1;
}

---

lower_bound

----

要是內容有重複

----

<table>
<colgroup span="7" style="background-color: gray;"></colgroup>

<tr>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
</tr>
<tr>
<td>1</td>
<td>3</td>
<td>4</td>
<td>4</td>
<td>4</td>
<td>7</td>
<td>8</td>
</tr>

</table>

----

重複中最小的

----

找最小的
<table>
<colgroup span="2" style="background-color: gray;"></colgroup>
<colgroup span="1" style="background-color: red;"></colgroup>
<colgroup span="4" style="background-color: gray;"></colgroup>

<tr>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
</tr>
<tr>
<td>1</td>
<td>3</td>
<td>4</td>
<td>4</td>
<td>4</td>
<td>7</td>
<td>8</td>
</tr>

</table>

----

<table>
<colgroup span="2" style="background-color: gray;"></colgroup>
<colgroup span="1" style="background-color: red;"></colgroup>
<colgroup span="4" style="background-color: black;"></colgroup>

<tr>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
</tr>
<tr>
<td>1</td>
<td>3</td>
<td>4</td>
<td>4</td>
<td>4</td>
<td>7</td>
<td>8</td>
</tr>

</table>

----

<table>
<colgroup span="2" style="background-color: black;"></colgroup>
<colgroup span="1" style="background-color: red;"></colgroup>
<colgroup span="4" style="background-color: black;"></colgroup>

<tr>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
</tr>
<tr>
<td>1</td>
<td>3</td>
<td>4</td>
<td>4</td>
<td>4</td>
<td>7</td>
<td>8</td>
</tr>

</table>

----

<table>
<colgroup span="2" style="background-color: gray;"></colgroup>
<colgroup span="1" style="background-color: green;"></colgroup>
<colgroup span="4" style="background-color: gray;"></colgroup>

<tr>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
</tr>
<tr>
<td>1</td>
<td>3</td>
<td>4</td>
<td>4</td>
<td>4</td>
<td>7</td>
<td>8</td>
</tr>

</table>

----

int binary_search_left(vector<int> &nums, int target)
{
    int l = 0;
    int r = nums.size() - 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (nums[mid] >= target)
        {
            printf("%d %d\n", l, r);
            r = mid - 1;
            printf("%d %d\n", l, r);
        }
        else if (nums[mid] < target)
        {
            printf("%d %d\n", l, r);
            l = mid + 1;
            printf("%d %d\n", l, r);
        }
    }
    return l;
}

---

upper_bound

---

int binary_search_right(vector<int> &nums, int target)
{
    int l = 0;
    int r = nums.size() - 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (nums[mid] >= target)
        {
            printf("%d %d\n", l, r);
            r = mid - 1;
            printf("%d %d\n", l, r);
        }
        else if (nums[mid] < target)
        {
            printf("%d %d\n", l, r);
            l = mid + 1;
            printf("%d %d\n", l, r);
        }
    }
    return l;
}

----

尋找第一個，大於你尋找的值的指標

---

田忌賽馬

----

今以君之下駟與彼上駟，取君上駟與彼中駟，取君中駟與彼下駟。

----

1 2 3
2 3 1

----

你和齊王各有N匹馬要比賽，齊王的馬由慢到快，速度不會變快。你的馬一開始速度是$a_i$成長率是$b_i$，經過$m$天速度會變為$a_i+m*b_i$

----

先想怎麼算贏幾個人

bool win(long long day)
{  
    int it = 0,sum = 0;  
    for(int i=0;i<n;i++) curr[i] = mine[i]+day*develop[i];  
    sort(curr, curr+n);  
    for(int i=0;i<n;i++)
    {  
        if(curr[i]>enemy[it])
        {  
            sum++;  
            it++;  
        }  
    }  
    return (sum>=k);  
}  

---

int main(){  
    scanf("%d", &t) 
    while(t--)
    {  
        upper = 100000000;lower = -1;  
        scanf("%d", &n)
        
        for(int i=0;i<n;i++)
        {  
            scanf("%d %d", &a, &b); 
        }  
        for(int i=0;i<n;i++)
        {  
            scanf("%d", enemy[i])
        }  
        sort(enemy, enemy+n);  
        if(!win(upper))cout<<-1<<endl;  
        else
        {  
            while(upper-lower!=1)
            {  
                M = (upper+lower)/2;  
                if(win(M))upper = M;  
                else lower = M;  
            }  
            cout<<upper<<endl;  
        }  
    }  
}  

---

## 基地台(apcs 20170304-4)

----

題目：https://zerojudge.tw/ShowProblem?problemid=c575
以k個基地台覆蓋n個服務點
問最少幾個點

----

bool canCover(int d)
{
    int coverage = P[0] + d;
    int cnt = 1;
    for (int i=1; i<N; i++)
    {
        while(P[i] > coverage)
        {
            coverage = P[i] + d;
            cnt++;
        }
    }
    return (cnt <= K);
}

----

int main() 
{
    cin >> N >> K;
    for (int i=0; i<N; i++) cin >> P[i];
    
    sort(P, P+N);
     
    int l = 0;
    int r = (P[N-1] - P[0]) / K + 1;
    int mn = 2e9;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if (canCover(mid))
        {
            mn = mid;
            r = mid;
        } 
        else 
        {
            l = mid + 1;
        }
    }
    cout << mn << '\n';
     
    return 0;
}

---

常見問題

----

"Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" — Donald Knuth

----

from java.util.Arrays.binarySearch

public static int binarySearch(int[] a, int key)
{
    int low = 0;
    int high = a. length - 1;
    
    while(low <= high)
    {
        int mid = (low + high) / 2;
        int midVal = a[mid];
        
        if(midVal < key)
            low = mid + 1;
            
        else if(midVal > key)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

----


---

#include <cstdio>
int search(int arr[], int n, int val)
{
    int left = 0, right = n, mid;
    while(left < right)
    {
        mid = (left + right) / 2;
        
        if(arr[mid] > val) right = mid - 1;
        else if(arr[mid] < val) left = mid + 1;
        else return mid;
    }
    return -1;
}

int main( )
{
    int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 13, 19 };
    
    int key = search(arr, 10, 1);
    
    printf("%d\n", key);
}

---

<= 寫成 < 找不到

---

#include\<algorithm\>
std::

binary_search(first, last, value);

upper_bound(first, last, value);

lower_bound(first, last, value);