19 June 2023

Intuition of Binary Search

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

• finding an exact element
• finding an element which satisfies a series criteria

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

or

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:

• true - meaning that the value is a positive integer, but we do not know if it’s the first or not yet. One thing for sure whatever is to it’s right is not required now. Either the value we are at as mid position is the first integer or some value to it’s left. Nothing towards the right. So we now update boundaries as r = mid
• false - meaning that the value is a negative integer. No chance of it becoming the value we are looking for meaning we can discard it. Hence the boundary update happens as l = mid + 1

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.