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?

Before contest

Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

02:31:14

Register now »

Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

02:31:14

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3803 |

2 | jiangly | 3707 |

3 | Benq | 3627 |

4 | ecnerwala | 3584 |

5 | orzdevinwang | 3573 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | Radewoosh | 3542 |

9 | jqdai0815 | 3532 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | awoo | 161 |

2 | maomao90 | 160 |

3 | adamant | 157 |

4 | maroonrk | 154 |

5 | -is-this-fft- | 148 |

5 | SecondThread | 148 |

7 | Petr | 147 |

7 | atcoder_official | 147 |

9 | TheScrasse | 145 |

9 | nor | 145 |

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?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/18/2024 15:03:48 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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?

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

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.