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?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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?
Название |
---|
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.