---
tags: 基礎算法
title: 二分搜&三分搜
---

:::info
#### 模板題 [ZJ d732](https://zerojudge.tw/ShowProblem?problemid=d732)
#### APCS歷屆 [ZJ c575](https://zerojudge.tw/ShowProblem?problemid=c575)
#### APCS歷屆 [ZJ h084](https://zerojudge.tw/ShowProblem?problemid=h084)
#### [CF #274 PB](https://codeforces.com/problemset/problem/474/B)
#### [TIOJ 1432](https://tioj.ck.tp.edu.tw/problems/1432)
:::

:::success
# 二分搜 Binary Search

## 問題
- 從一堆數字中找一個特定數字，若存在則輸出1，不存在輸出0
- n個數字，K筆詢問
- $1<=n<=10^5$ $1<=K<=10^5$

### 爆搜解

- 一個一個檢查
- 複雜度：$O(nK)$

### 二分搜解

## 前提

- 函數遞增/遞減(具單調性)，且有上下界

### 實作
- 三個指針$l$, $m$, $r$, $l\le m\le r$
- 判斷m與所求大小關係，縮小範圍
- 停止條件：$m$為答案 or $l==r$
- 初始化（遞增）：$l=下界， r=上界$， $m=(l+r)/2$
- 複雜度：$O(K\log n)$

## ZJ c575 詳解

- 先找前提 -> 上下界、單調性
- 上界：一個蓋所有 -> $MAX(P[i])$
- 下界：0
- 單調性：顯然直徑越大，所需基地台越少
- 對直徑二分搜
- 檢查是否成立：greedy想法，每個基地台最左端為一服務點，從下一個未覆蓋服務點開始放(不浪費覆蓋範圍)

## 二分搜在求比率極值問題上的應用

### 問題

- 有一集合$S$包含$n$個元素，每個元素$e$有$W(e)$和$T(e)$兩個值，今從中選出$m$個，使得$$\frac{\sum_{e_\in S}W(e)}{\sum_{e\in S}T(e)}$$有最小值
- 求$min(\frac{\sum_{e_\in S}W(e)}{\sum_{e\in S}T(e)})$($m$個)

### 理論

- 對於任一比率$r$，如果我們能判斷是否存在$\frac{\sum_{e_\in S}W(e)}{\sum_{e\in S}T(e)}\le r$，便可以對答案二分搜來找到足夠小的答案
- https://web.ntnu.edu.tw/~algo/SpanningTree2.html#4

### 實作

- 移項得$\sum_{e_\in S}W(e)\le r\sum_{e\in S}T(e) \Rightarrow \sum_{e\in S}[W(e)-rT(e)]\le 0$
- 對於目前的比率r，計算每個元素$e$的$W(e)-rT(e)$，若找得到一組$m$個元素使得$\sum[W(e)-rT(e)]\le 0$，則將右界左移，若找不到，則將左界右移

### 題目
1. [Desert King](https://icpcarchive.ecs.baylor.edu/external/34/3465.pdf)
2. [Minimal Ratio Tree
](https://icpcarchive.ecs.baylor.edu/external/43/4326.pdf)
:::

:::info
#### [CF #320 PC](https://codeforces.com/contest/578/problem/C)
#### [神秘的題目](https://open.kattis.com/problems/jewelrybox)
:::

:::success
# 三分搜 Ternary Search

## 用途

- 找二次(U型)函數極值

## 實作

- 四個採樣點 $l$, $m_1$, $m_2$, $r$
- 初始化 $l=$下界, $r=$上界, $m_1=\frac {(l+r)}{2}$, $m_2=\frac {(r+m_1)}{2}$
- 設函數$f(n)$為$x=n$所對應的$y$值
- 開口向上

case1 : $f(l)<f(m1)<f(m2)<f(r)$ $r$往左

case2 : $f(l)>f(m1)<f(m2)<f(r)$ $r$往左

case3 : $f(l)>f(m1)>f(m2)<f(r)$ $l$往右

case4 : $f(l)>f(m1)>f(m2)>f(r)$ $l$往右

- 判斷大小關係，遞迴逼近
:::