Binary Seach, 倍增法
===
###### tags: `Algorithm`

## 整數二分搜

***以搜8為例***

### upperBound_a, lowerBound_a

* 排除右邊
* lw_a 向右排除 >=
* up_a 向右排除 >
* ` m = (l+r+1)>>1 ` 避免 m 一直留在左邊進入無窮迴圈

// seaching up_a
int l, r, m;
while (l<r)
{
    m = (l+r+1)>>1;
    if (arr[m] > tar)
    {
        r = m-1;
    }
    else
    {
        l = m;
    }
}
retunr l;

### upperBound_b, lowerBound_b

* 排除左邊
* lw_b 向左排除 <
* up_b 向左排除 <=
* ` m = (l+r)>>1 ` 避免 m 一直留在右邊進入無窮迴圈

// seaching lw_b
int l, r, m;
while (l<r)
{
    m = (l+r)>>1;
    if (arr[m]<tar)
    {
        l = m+1;
    }
    else
    {
        r = m;
    }
}
return l;

## 實數的二分搜

==設定比題目要求小的區間, 左加右減直到 `l>r`==

實數二分搜不用那麼嚴謹, 只要確保搜的精度比題目高, 那捨去後答案都是一樣的

### UVa 15516 WIFI

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for( int i=(a); i<(b); i++)
#define DE cout << " ::"

#define EPS 1e-2
#define maxM 100010

int hou[maxM];
int ap, m;

bool canDo( double r){
    double i = hou[0];
    int amnt = 0;
    while( i <= hou[m-1]){
        i = *lower_bound( hou ,hou+m, i);
        i += r;
        amnt++;
    }
    return amnt<=ap;
}

int main(){
    int T; cin >> T;
    while( T--){
        memset( hou, 0, sizeof( hou));

        cin >> ap >> m;
        REP( i, 0, m) cin >> hou[i];
        sort( hou, hou+m);

        double l = 0, r = hou[m-1], ans;
        while( l < r){
            ans = ( l+r) /2;
            if( canDo( ans)){
                r = ans-EPS;
            }
            else{
               l = ans+EPS;
            }
        }
        cout << fixed << setprecision(1) << ans/2 << '\n';
    }

}

## 倍增法

### 提示
* 站在左邊戳 N 步位置
* 如果成功 -> 位移過去
* 如果失敗 -> 步數砍半
* 直到步長為0
* 最後會停在失敗的前一格

inline bool suc(int i, int x)
{
    return arr[i]>x; // upper bound a
    
    // return arr[i]>=x; // lower bound a
}

int s, i;
while (s>0)
{
    if (i+s<n&&suc(i+s,x))
    {
        i+=s;
    }
    else
    {
        s>>=1;
    }
}