Binsearch not updating
When you encounter a problem which you think could be solved by applying binary search, you need some way of proving it will work.
I will now present another level of abstraction which will allow us to solve more problems, make proving binary search solutions very easy and also help implement them.
Notice how index 7 (where the target value is located) is the first for which the predicate yields yes, so this is what our binary search will find.
One important thing to remember before beginning to code is to settle on what the two numbers you maintain (lower and upper bound) mean.
The logarithm is an awfully slowly growing function.
In case you’re not aware of just how efficient binary search is, consider looking up a name in a phone book containing a million names.
If you could manage a list containing all the people in the world sorted by name, you could find any person in less than 35 steps.The power of binary search begins to show now: not only do we need at most O(log N) comparisons to find the target value, but we also do not need to evaluate the function more than that many times.