B4题解

二分查找

Code

#include<stdio.h>
inline int ask(int y){ // 自己实现类似B3的ask函数
    printf("? %d\n",y); // 询问
    fflush(stdout); // 刷缓冲
    char state;
    scanf("\n\n%c",&state); // 获取状态
    if(state=='=') return 0;
    else if(state=='>') return 1;
    else return -1;
}
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){ // 如果一样，返回
            return m;
        }
        else if(state>0){ // 如果比m大，l右移
            l=m+1;
        }
        else{ // 如果比m小，r左移
            r=m-1;
        }
    }
    if(l==r) return l; // 重叠了就是找到了
    if(l==r-1){ // 如果差一，不是l就是r
        if(!ask(l)) return l;
        return r;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    int ans=guess(n);
    printf("! %d",ans); // 输出
    fflush(stdout);
    return 0;
}