# 二分法
## 整數二分查找(O(logn))
### 不可重復數列二分查找
```C++
// A[] 為不重復遞增數列，x 為需要查找的值
int binarySearch(int A[], int left, int right, int x){
int mid;
while(left<=right){
mid=left+(right-left)/2; // 防止溢出
if(A[mid]==x) return mid;
else if(A[mid]>x) right=mid-1;
else left=mid+1;
}
return -1;
}
```
### 可重復數列二分查找
假設目標值 x 分布在 [L, R) 之間，則可分別查找 L 和 R
```C++
// A[] 為可重復遞增數列，查找第一個大于等于 x 的數
int lower_bound(int A[], int left, int right, int x){
int mid;
while(left<right){// left==right 時，找到唯一位置
mid=left+(right-left)/2;
if(A[mid]>=x) right=mid;
else left=mid+1;
}
if(A[right]>=x) return left;
else return -1;
}
```
```C++
// A[] 為可重復遞增數列，查找第一個大于 x 的數
int upper_bound(int A[], int left, int right, int x){
int mid;
while(left<right){
mid=left+(right-left)/2;
if(A[mid]>x) right=mid;
else left=mid+1;
}
if(A[right]>x) return left;
else return -1;
}
```
### 尋找可重復數列中滿足條件 C 的元素位置
查找可重復數列中滿足條件 C 的元素位置可以分解為
- 查找第一個滿足條件 C 的數 L
- 查找第一個滿足條件 C 的數起，第一個不滿足條件 C 的數 R
- 滿足條件 C 的元素位置為 [L, R)
```C++
// A[] 為可重復遞增數列，查找第一個滿足條件 C 的數
int lower_bound(int A[], int left, int right){
int mid;
while(left<right){
mid=(left+right)/2;
if(C(mid)) right=mid;
else left=mid+1;
}
if(C(right)) return left;
else return -1;
}
// 查找第一個滿足條件 C 的數起，第一個不滿足條件 C 的數
int upper_bound(int A[], int left, int right){
left=lower_bound(A, left, right);
if(left==-1) return -1;
else(left==right) return right+1;
int mid;
while(left<right){
mid=(left+right)/2;
if(!C(mid)) right=mid;
else left=mid+1;
}
return left;
}
```
## 二分法拓展
將二分查找的范圍從整數拓展到實數時，判斷是否找到需要考慮精度。
```C++
// 求實數范圍 [left, right] 上，遞增函數 f(x)=0 的解
double solve(double left, double right){
const double eps=1e-5;
while(right-left<eps){
mid=(left+right)/2;
if(f(x)>0) right=mid; // f(x) 遞減，則改為 <0
else left=mid;
}
return mid;
}
```
## 快速冪
給定三個正整數 $$a,b,m\ (a<10^9,b<10^18,1<m<10^9)$$ ，求 $$a^b\%m$$
#### 循環寫法（O(b)）
```C++
typedef long long LL;
LL power(LL a, LL b){
a%=m;
LL ans=1;
for(int i=0;i<b;i++){
ans=ans*a%m;
}
return ans;
}
```
#### 遞歸寫法（O(logb)）
```C++
typedef long long LL;
LL power(LL a, LL b){
a%=m;
if(b==0) return 1; // b=0 時，a^0=1
// b 為奇數，轉換為 b-1
if(b%2==1) return a*power(a,b-1,m)%m;
else {// b 為偶數，轉換為 b/2
LL mul=power(a,b/2,m);
return mul*mul%m;
}
}
```
#### 迭代寫法（O(logb)）
```C++
typedef long long LL;
LL power(LL a, LL b){
a%=m;
LL ans=1;
while(b>0){
if(b&1){// 若 b 的二進制末位為1，則 true(等于 b%2)
ans=ans*a%m;
}
a=a*a%m;
b>>=1; // 將 b 的二進制右移1位(等于 b/=2)
}
return ans;
}
```
## ChangeLog
> 2018.09.03 初稿
