B3题解

不完全普通的二分查找

复杂度

时间复杂度:

$O(logn)$

空间复杂度:

$O(1)$

Code

#include"guess.h"
int guess(int n)
{
    int l=1,r=n; 
    while(l!=r&&l!=r-1){
        int m=(l+r)>>1;
        int state=ask(m);
        if(state==0){ // 如果一样，返回
            return m;
        }
        else if(state>0){
            l=m+1; // l右移
        }
        else{
            r=m-1; // r左移
        }
    }
    if(l==r) return l; // 重叠了就是找到了
    if(l==r-1){ // 如果差一，不是l就是r
        if(!ask(l)) return l;
        return r;
    }
}