4 ms·
True, but only if the list has more than 2^31 entries on a 32-bit machine. In practise that's not possible if it contains 32-bit integers because that would ta
by rrrlasse 11y ago
True, but only if the list has more than 2^31 entries on a 32-bit machine.
In practise that's not possible if it contains 32-bit integers because that would take up a 16 GB linear address space which doesn't exist on a 32-bit machine.
An academically correct version would be `size_t probe = low + ((high - low) / 2);` but that would be much slower.
You could instead just add an initial debug-mode-only assert on the list length, for correctness.
- maxlybbert 11y agoSun had to put out a JDK bug fix for this nine years ago ( http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-... ).