4 ms·

Jon Bentley showed this can have problems with overflow. Better, mid = left + (right - left)/2; https://en.wikipedia.org/wiki/Binary_search_algorithm#Implemen

• bogomipz 9y ago
  I don't believe Python has this problem though as it will automatically promote a fixed sized int to an arbitrary precision int if the former isn't sufficient. See: https://stackoverflow.com/questions/4581842/python-integer-ranges https://stackoverflow.com/questions/4581842/python-integer-r...
  • wiz21c 9y ago
    Yep, that's why I didn't raise the point. Now, Python can certainly not represent number of infinite sizes... I'll add that the super cool thing about "simple" algorithms such as binary search is that their practical application is full of edge cases which are very interesting to study to properly understand what these algorithms "mean". There's an awful lot to be said about even the simplest things.