search

ovidiuch / illustrated-algorithms

Interactive algorithm visualizations
https://algorithms.now.sh
MIT License
2.77k stars 166 forks source link

Binary search improvement #21

Closed mukhtar closed 7 years ago

mukhtar commented 7 years ago

Firstly, awesome project.

I remember reading that it's common in many implementations of binary search to calculate the midpoint as such

mid = (low + high) / 2

which is how it's calculated here.

The has a subtle issue (as discussed here) in that it can lead to overflow if low and high are sufficiently large enough. One way to avoid this is to calculate the midpoint as such

mid = low + ((high - low) / 2)

This is obviously not an issue in the illustration which is searching through a list of 6 animals, however it might be worth updating the implementation for general correctness. Thoughts?

ovidiuch commented 7 years ago

Integrated this in a new Footnotes section. Also added a Disclaimer to define the scope of the project better. Hope this helps. Thanks!