Menu
What's the difference between this two formulas
mid = low + (high - low) / 2;
mid = (high + low) / 2;
633
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.
Binary Search is a searching algorithm for finding an element's position in a sorted array. In this approach, the element is always searched in the middle of a portion of an array. Binary search can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.
Mathematically Maximum iteration possible (Assuming case of only integer type) is = ceil( log2 ( initial_r - initial_l ) ) base of log is 2 because every time we are diving our range in half by taking a mid and switching to one of the half.
Once the reasonable portion contains just one element, no further guesses occur; the guess for the 1-element portion is either correct or incorrect, and we're done. So with an array of length 8, binary search needs at most four guesses.
In the 2nd version, if high + low is greater than the maximum value of an int (assuming high is an int) then it can overflow, invoking undefined behavior. This particular bug is solved with the 1st version.
There are still issues with the 1st version, e.g. if low is a very large negative number, the difference can still overflow.
From c++20, you should use std::midpoint for this, which handles a whole bunch of corner cases, and does the right thing for all of them.
This seemingly simple function is actually surprisingly difficult to implement, and in fact, there's an hour long talk given by Marshall Clow at cppcon 2019, that covers the implementation of just this function.
174
The first one is superior (although still not perfect, see Binary Search: how to determine half of the array):
It works in cases where addition is not defined for high and low but is defined for adding an interval to low. Pointers are one such example, an object of a date type can be another.
high + low can overflow the type. For a signed integral type, the behaviour is undefined.
44
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
