Binary Search —Basics and beyond

Today we are going to look at the explore the technique called Binary Search. Binary Search is a technique that works on sorted arrays, when the numbers are sorted you can make certain decisions which help optimize the algorithm a lot.

Linear Search:

Array with Integer numbers.

Suppose the problem statement is to find the number ‘9’ if it exists in the array or not, then we just walk through the elements one by one and check if it exists and return the index when you find it. A basic for loop would be suffice to get the job done for this one. Of course we have to handle the case of what happens if the number does not exist in the array.

Let’s look at the code to do it,

When it comes to time complexity of the above program we are looking at O(N). Assume the number exists at the end of the array then we have to walk through the entire array to find the number.

Binary Search:

We can easily cut down this time to O(logn) if the array is sorted, Let’s take a look at how the sorted array would look like.

I have went ahead and highlighted on how the search happens in order to reach the desired number. The intuition is you have the whole array that you can search and you start in the middle. This is done by the following snippet of code,

int middleIndex = (startIndex + endIndex) / 2

The initial values of startIndex = 0, endIndex = 6, so we get middleIndex = 3. We evaluate the condition on whether 5 > 9 or 5 < 9. Since 5 < 9 all the numbers below 5 can be eliminated from your searching as those numbers will be lesser than 5 since the array is sorted, So effectively modify your search space from startIndex = 0, endIndex = 6 to startIndex =4, endIndex = 6.

Repeating the same process with startIndex = 4, endIndex = 6 we have
middleIndex = 5, we know that 8 < 9. So we further modify the search space as startIndex =6 and endIndex = 6.

Repeating the same process with startIndex = 6, endIndex = 6 we have middleIndex = 6, we know that 9=9(Voila! The number that we are looking for). So at this point we end the search and return the index of number 9. The observation here is that if we have to do a manual search on this sorted array, we would have gone through the entire array(7 steps) to find the element which exists towards the entire array. Instead when we applied the binary search technique it took us 3 steps to reach there.

log2(7)= 2.807355

So the above equation also proves that why the binary search is O(logn) as we cut down on the number of steps to reach the number you want to find. Let’s take a look at the code to do this.

Binary Search — Problem:

Given an integer array nums sorted in ascending order, and an integer target.
Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You should search for target in nums and if you found return its index, otherwise return -1.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Source: Leetcode

Since we already touched upon the Binary Search in the above example it will feel intuitive when we apply the same technique to this problem. This problem introduced one caveat of the array is rotated at some pivot unknown to us, hence we need to account for that use case.

Bring back the thinking of Binary search where when you land at a particular index we have enough information to make a decision on whether to navigate left or to navigate right. In this case there has to be additional checks,

Assume that you land in a random middle index and you need to check for these two things,

Is the left half sorted,
if (nums[left] <= nums[middle]) { 
//Check whether the number we are searching for falls between the left and the middle element.
 if (target >= nums[left] && target <= nums[middle]) {
    //Search for number in left half.
 } else {
   //Search for number in right half.
 }
}
Is the right half sorted,
if (nums[middle] <= nums[right]) { 
//Check whether the number we are searching for falls between the middle and the right element.
 if (target <= nums[right] && target >= nums[middle]) {
    //Search for number in right half.
 } else {
   //Search for number in left half.
 }
}

The else conditions are additional things you added here to handle the cases of where the array is rotated at some pivot, but these checks are more than sufficient evidence to proceed to a particular direction.

Putting it all together in the code,

Note that I have added some interesting way of finding the middle index, this can be applied to avoid overflow in your calculations.

I would highly suggest walking through the above code with examples to understand and develop the intuition of why it works the way it works. See you all with another good Algorithm topic next time.

Happy learning!