Intuition of Binary Search

The requirement is to have the array sorted. Search could be of two scenarios

Series criteria - given a series of numbers find an element which starts a criteria. For example first positive integer. An element which starts a specific trend defined by some function f(x).

We always start with

l = 0
r = n-1

We keep the exit condition

l < r

We calculate the mid as

mid = (r+l)/2

Then each time we check if a[mid] satisfies the criteria.

The discarding criteria comes into play depending on the type of search. If we are looking for an exact value i.e if we know the value before hand we can discard including the value at the mid position which results in changing the boundaries like below

l = mid + 1


r = mid - 1

Here we can completely get rid of mid

But if we know only of a criteria or a condition and we need to find the value that starts a trend then we have two situations. Consider we take the example of finding first positive integer. We have a function f(x) which gives true or false for that condition.

Now, if we are checking an arbitrary mid value we can have two outcomes:

Here unlike the previous scenario we cannot discard mid, because depending on the condition check the mid value can either become can be or a probable value. So in such cases we just update the right boundary to be mid keeping the probability that this value maybe what we seek. In the alternate case when the criteria returns false we sure shot know that this value has no chance for us. Thus, the pattern will be if it’s false discard otherwise the value has a probability so we should consider the boundary update to be inclusive. The major thing to note here is that our result will not be found in the loop, when the loop ends, whatever value the left boundary holds is what we seek.