比较简单的二分

思路

特判+二分

代码

#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)$