2 ms·
In the binary search algorithm : mid = (left + right) // 2 It would be nice to have a discussion on why you used // instead of /. Depending on who reads your
by wiz21c 9y ago
In the binary search algorithm :
mid = (left + right) // 2
It would be nice to have a discussion on why you used // instead of /. Depending on who reads your code, explaining this "obvious" choice might be interesting.
There are also other discussions topic : what happens if the array is empty ? what happens if the array is twice the size of the computer's RAM ? What happens if all the numbers in the array are equal ?
- gshubert17 9y agoJon Bentley showed this can have problems with overflow. Better, mid = left + (right - left)/2; https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem...
- bogomipz 9y agoI 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 agoYep, 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.