fischerman's blog

By fischerman, history, 8 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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$$$.

»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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.