比较简单的二分

思路

特判+二分

代码

#include "guess.h"
#include <iostream>
using namespace std;

int guess(int n) {
    int low = 1;
    int high = n;
    while (true) {
        if (low == high) return low;
        int mid = (low + high)/2;
        int result = ask(mid);
        if (result == 0) return mid;
        else if (result < 0) high = mid-1;
        else low = mid+1;
    }
}

复杂度

时间复杂度:

$O(log_2 n)$

空间复杂度:

$O(n)$

B3 猜数

提供一种乌七八糟的做法。。。

思路

正常的二分，当我们猜大了或猜小了缩小区间，直到我们猜到为止。

但是此题我的做法竟然非常玄学，大家待会看看代码。

解题方法

我是这么乱搞der：

首先，写出我的代码：

#include "guess.h"

int guess(int n) {
    int l = 1, r = n;

    while (true) {
        int mid = (l+r) / 2;
        int ques = ask(mid);

        if (ques == 0) {
            return mid;
        }

        if (ques == 1) {
            l = mid;
        } else {
            r = mid;
        }
    }
}

提交，发现只有 20 pts.

其中，WA的4个点都是猜多了1次。

怎么办？我们想到，中心点可能还有一个，既然总是猜多，那可能是我们运气不好。不如猜可能的另外一个中心点？

动手试试：

#include "guess.h"

int guess(int n) {
    int l = 1, r = n;

    while (true) {
        int mid = (l+r) / 2+1;
        int ques = ask(mid);

        if (ques == 0) {
            return mid;
        }

        if (ques == 1) {
            l = mid;
        } else {
            r = mid;
        }
    }
}

分数上升至 80 pts.

还有一个点，我们从测试反馈里看出正解是只猜0次的，不难想到可以在开头加个特判。

直接AC，具体看代码。

复杂度

时间复杂度:

$O(\text{log}_2n)$

空间复杂度:

$O(n)$

Code

#include "guess.h"

int guess(int n) {
    int l = 1, r = n;

    if (l == r) {
        return 1;
    }

    while (true) {
        int mid = (l+r) / 2+1;
        int ques = ask(mid);

        if (ques == 0) {
            return mid;
        }

        if (ques == 1) {
            l = mid;
        } else {
            r = mid;
        }
    }
}

标题B3

简单！

Code

#include "guess.h"
#include <iostream>
using namespace std;

int guess(int n) {
    int low = 1;
    int high = n;
    while (true) {
        if (low == high) return low;
        int mid = (low + high)/2;
        int result = ask(mid);
        if (result == 0) return mid;
        else if (result < 0) high = mid-1;
        else low = mid+1;
    }
}

标题B3

Code

#include "guess.h"
#include <iostream>
using namespace std;

int guess(int n) {
    int low = 1;
    int high = n;
    while (true) {
        if (low == high) return low;
        int mid = (low + high)/2;
        int result = ask(mid);
        if (result == 0) return mid;
        else if (result < 0) high = mid-1;
        else low = mid+1;
    }
}

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;
    }
}