-
Notifications
You must be signed in to change notification settings - Fork 3.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
A problem in many binary search implementations #92
Comments
Good to know, which language/languages can this be an issue? |
C/C++, Java, etc |
Is there any example? |
You have to round the mid number down manually |
Maybe it's better to use binary shift operator instead of dividing by two and type conversions? I guess most of all programmic languages have it. I used it, during the grokking binary search algorythm: $mid = ($low + $high) -shr 1
(0 + 5) -shr 1 # 2, ok
(0 + 7) -shr 1 # 3, ok There is a problem with the conversion from float to integer, for example, PoSh round a float to nearest even, not to down: [int]( (0 + 5) / 2 ) # 2, ok
[int]( (0 + 7) / 2 ) # 4, expect 3 |
The problem is in the assignment
It can lead to overflow in some language
The text was updated successfully, but these errors were encountered: