Блог пользователя fischerman

Автор fischerman, история, 4 года назад, По-английски

A weird though came to my mind while writing binary search that why don't we use the geometric mean of start and end instead of arithmetic mean, I mean what would be the time complexity and why don't we use it?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

With binary search, we are able to cut our search space in half if we know the result in the middle. If we took the geometric mean, we wouldn't get this advantage?

int n = 1000000;

bool check(int m) {
    return m == n;
}

int main() {
    int l = 0; 
    int r = n;
    int ans = -1;
    int cnt = 0;
    
    while (l <= r) {
        int m = (l + r) / 2;
        cnt++;
        if (check(m)) {
            ans = m;
            r = m - 1;        
        } else {
            l = m + 1;
        }
    }
    
    cout << cnt << '\n';
}

This prints out 20 iterations, but if we replaced the calculation of m with int m = sqrt(1LL * l * r);, it gives us 26 iterations. This is not really a small difference, but why use it?

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

If the current range is of length $$$n$$$, you have to pick a value $$$x$$$ that minimizes $$$\max(n-x,x)$$$, that is $$$\frac n 2$$$.

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Your idea is perfectly valid for problems where you need to print a real number with given relative precision, and it's in fact optimal.