fischerman's blog

Doubt in binary search algorithm
By fischerman, history, 4 years 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

»
4 years 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?

→ Reply
»
4 years 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$$$.

→ Reply
»
4 years 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.

→ Reply