Understanding binary search: A super-simplified explanation

Fundamentals and some examples in python

XQ
XQ
Nov 17, 2021 · 5 min read

Searching for something from a data structure is a pretty common thing. We search for files, people, posts, etc. Most websites and applications have a search bar.

When it comes to problem-solving, searching for some element can be an important intermediary or actionable step. Here, we explore some fundamentals of searching algorithms.

  • If you have an array of n elements, the simple way to find out if an element x exists in that array is to write a for loop.

As with any programming question, we want to optimize this. How?

We have a special scenario in case the array in question is a sorted array. That’s where binary search comes into play. Let us see how we can take advantage of the structure of a sorted array to perform a more efficient search.

  • We know that in a sorted array, all elements less than x will be to its left and those greater than x will be to the right.
case 1: if x < m then x is to the left of middle.
case 2: if x > m then x is to the right of middle.
case 3: x = m and hence we can return the index of middle.
  • In case 1, x is somewhere in the subarray[0:m-1]. Can we repeat the same process again? Let’s find the middle element of this new subarray and compare it with x. By doing that we can determine the new sub-subarray where x is located in.

Let’s do a dry run on a sample array to get the feel of how binary search is happening.

  • Let’s say we have a sorted array = [11, 12, 13, 14, 15, 16, 17, 18, 19, 20].

Let us test our understanding further by solving a Leetcode problem. We will write code for the logic discussed above.

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

  • In this question, we are given a list of lists and we have to find if the target number is present in that input matrix.

Here’s the python solution for the same. Do read the code comments and introspect on what’s happening.

Now that you have a fundamental understanding, try out this question on Leetcode by yourself. If possible, try to implement the solution in both python and javascript.

To test your understanding further you can try this problem too. You can solve it directly via binary search with some minor tweaks to the return statement.

Remember the fundamental search approach:

1. Find out if a target element is to the left or right side of the middle element.2. Store the first and last index as variables and update them to create new subarrays where the target element might be present.3. Repeat this process till the middle element becomes equal to the target element.

The Research Nest

Empowering humanity with exclusive insights.