Menu
So, the correct way of calculating mid in a binary search is mid = low + ((high - low) / 2) in order to handle overflow errors.
My implementation uses unsigned 64 bit variables and I don't ever see a situation where my arrays get so big so as to cause an overflow. Do I still need use the above implementation or can I use mid = (low + high) / 2
What's best practice here?
599
Given a sorted array, we find the middle-most element and check the element with the key. If the middle-most element is equal to key, we've found the key. If the middle-most element is greater than the key, we search on the left half of the middle-most element, else we search on the right half.
Measure the distance between the two end points, and divide the result by 2. This distance from either end is the midpoint of that line. Alternatively, add the two x coordinates of the endpoints and divide by 2. Do the same for the y coordinates.
The value of low cannot be greater than high; this means that the key is not in the vector. So, the algorithm repeats until either the key is found or until low > high, which means that the key is not there. The following function implements this binary search algorithm.
If there is no possibility of overflow, the overflow-safe way of computing the midpoint is technically unnecessary: you can use the unsafe formula if you wish. However, it's probably a good idea to keep it there anyway, in case that your program gets modified some day to break your assumptions. I think that adding a single CPU instruction to make your code future-proof is a great investment in maintainability of your code.
139
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
