Quick Decode of Binary Search | Different Use Cases | Python

Photo by Markus Winkler on Unsplash

As we already aware of, searching an array/list for a number is something we happen to do every now and then in our daily jobs. For that, we also have so many libraries and utility functions to help us search instead of writing all the code ourselves. So why this article?

Well. This article purely articulates my understanding of how Binary search algorithm works. The deep dive is inspired from the fact that it can help us optimise so many different kind of coding questions (mentioned at the end of the article) where searching an entire array becomes necessary and we are not allowed to use Utility functions or we need to customise the search according to our needs.
An example of such scenario, as you already have guessed, is during coding interviews. So let’s start with the decode and understand its use cases.

NOTE: This article already assumes one to have basic understanding of Binary search in Sorted array and its advantage over Linear search with respect to time complexity of O(n log n).

Simple Binary Search:

Suppose we have a sorted array: arr = [1,2,3,4,6,7] . And we want to search a number n .

Code snippet of a simple Binary Search

Set the boundary right:

low and high decides the range of the search space. So in the above case for an array, index 0 to index len(arr)-1 gives the entire search space.

Now think, is it possible that in any case we have to search till index len(arr) ? Well, yes. When we want to search for an insert index instead of a number presence. Since at index len(arr) also, new element can be inserted. So search space will be from index 0 to index len(arr)

Set the Mid Index Right:

In the above code example, we are taking the lower or the floor value of the (low+high)//2 evaluation.

This makes sure we are always taking the low sided index or lower element in each iteration and not the left sided or high -er element in the array for comparison.

Hence, we reset our low index boundary to skip by 1 instead of high boundary in the if-else comparison evaluation.

In case, we want to take right indexed or higher element as the mid, we should take the ceil value of (low+high)/2 . In that scenario, we must skip high boundary by 1 (by resetting high = mid -1) and keep low as mid .

Code snippet for selecting ceil value for mid

Note: In other languages, expression (low+high)/2 can lead to overflow of the memory in case low and high are extremely huge numbers. In that case, it is advisable to do this instead: low+ ((high-low)/2) or (low+high)>>1 .

If and Else Conditions:

Taking example of below code snippet from simple binary search mentioned above:

We see a simple logic of if - else conditions where boundaries are being reset such that each time at least one element is eliminated from the search space.

If our number n to be searched is greater than arr[mid] element , we know we have to make the search space to the right of our mid index since it is a sorted array and greater elements would lie right to the array. So we reset out low to mid+1 . Thus eliminating mid
indexed element.

Otherwise, when our target number n is either equals to or less than arr[mid] element, we reset our high to mid to change the search space to left side where lower elements exists. Now how is this eliminating?
As already mentioned, we are taking the floor value for mid index which always yields the low index boundary and thus making sure high index gets eliminated when being reset to mid .

Whats wrong with this condition?

Well even when it looks logically correct, there is one minor problem with the above condition. Here, we are resetting high to mid when target n is lower than the mid value. In case the mid value is equals to target n , what is happening now? We are moving the low away from mid , thus losing the target n value which was matching with mid . Hence, this condition won’t yield correct result. As a result, we must make sure when mid is possibly equals to the target, we retain the mid .

NOTE: Since here we are taking lower indexed element when selecting mid , we are eliminating mid from low in if-else conditions. In case, you take higher indexed or ceil value index while selecting mid , eliminate mid from high boundary instead.

Closer Look?

Now wait. On closer look, aren’t we returning True or False immediately after matching with the number if present in the array?
Well, we could but are not. Rather we are setting the high boundary to mid one so that our while condition breaks only when we are left with one element in the search space, with low==high.

Definitely this will add extra iterations on the part of searching an element like in the cases:

arr = [1,2,3,4,5]
n = 3

Iteration loop will look like:

However, this will help establishing generic Binary search when we want to search for Insert Index or Parting Index( where a Pivot element exists ), instead of a particular element in the array.

In those cases simply, the insert index will be held by low or high boundary without much change in the code algorithm.

Brief on Binary Search Implementation Requirements:

• Decide the search space of binary search. This is the range we are looking for the answer to be in.
• Decide the condition by which the search space can shrink.
• Finally, shrink the search space.

Some Awesome References I have used understanding:

• https://leetcode.com/problems/binary-search/solutions/423162/Binary-Search-101-The-Ultimate-Binary-Search-Handbook/
• https://www.geeksforgeeks.org/binary-search/

Some Practice Problems:

• https://leetcode.com/problems/search-insert-position/ (Easy)
• https://leetcode.com/problems/koko-eating-bananas/ (Medium)
• https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ (Medium)
• https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ (Medium)

And that’s it for this article. Hope it helps customising Binary Search for different use cases.

Happy Coding! 🙌