二分查找（基于迭代）

一般用迭代实现二分查找，左闭右开。

int bsearch(int *A, int x, int y, int v){
    int m;
    while(x < y){
        m = x + (y-x)/2;
        if(v == A[m]) return m;
        else if(A[m] < v) x = m + 1;
        else y = m;                  //左闭右开 [x,y) 
    }
    return -1;
}

int lower_bound(int *A, int x, int y, int v){
    int m;
    while(x < y){
        m = x + (y-x)/2;
        if(A[m]>=v) y = m; //若等于则向左边逼近找最小界； 
        else x = m+1;
    }
    return x;
}

分析以上，A[m] = v,至少找到一个v，而左边还有可能有，因此区间变成[x,m]
A[m] > v,所求位置不可能在后面，但有可能是m，因此区间变为[x,m]
A[m] < v, m和前面都不可行，因此区间变为[m+1, y]

int upper_bound(int *A, int x, int y, int v){
int m;
while(x < y){
m = x + (x+y)/2;
if(A[m] <= v) x = m + 1;//若等于则向右边逼近找最大界
else y = m;
}
return x;
}