Capabilities of Binary Search Algorithm: Part-2

More than just a Searching Algorithm

Before starting this article, I want to take a moment to thank you guys for so much loving and support to the first part of this article, I got an amazing response on that and many people texted me saying it was amazing and they are eagerly waiting for the second part.

So yes, your wait is over, and let's get started!

Let’s recapitulate what all we have covered —

So last weekend, I released the first part of the article, “Capabilities of Binary Search Algorithm: Part-1” in which I introduced you with the famous searching algorithm known as Binary Search Algorithm. We also discussed how it mas be modified a little bit to do many things other than just searching.

We have already discussed some hidden capabilities of Binary Search Algorithm. Here is a list of the same : —

• Searching in Reversed Sorted Array.
• Finding First and Last Occurance an Element.
• Finding Floor and Ceil of an Element.
• Finding the peak of an array.

If you want to read the full article, here’s the link —

Capabilities of Binary Search Algorithm: Part-1

In this article we’ll be discussing the following : —

• Finding Square Root of a number.
• Number of times a Sorted array is rotated.
• Searching in Nearly Sorted Array.
• Finding a position on an Element in an infinite array.
• Searching in Bitonic Infinite Array.
• Searching in 2-D Array.

5. Finding Square Root of a number.

Here we’ll be finding power and square root of a number using Binary Search Algorithm.

Approach
For finding Square root of a number, we will keep start at 0 and end at n/2. Check if mid² == no, if yes, we found the element. else we will manipulate the start and end index accordingly

Code

6. Number of times a Sorted array is rotated.

In this problem, you’ll be provided with an unsorted array and you need to count how many times a Sorted array is rotated.

Approach
Finding index of the element which is greater than prev.

7. Searching in Nearly Sorted Array.

Here you’ll be provided with a nearly sorted array with shuffling up to 2 elements. You need to search element at an index in this suffered array. Here is an example:-

array => {1, 3, 2, 4, 6, 5, 7, 9, 8, 10}

index of 6 = 5

Approach
Normally we compare with the adjacent element, ie, mid+1 and mid-1 but in this case, we’ll search on mid+1 , mid+2, mid-1, mid-2 .

Code

8. Finding a position on an Element in an infinite array

In this question, you are given an infinite array and you are expected to search an element in the same.

Problem: You can’t take high as length-1

Approach
Here we’ll initially take high as 1 and increment it in an exponential order.

Code

9. Searching in Bitonic infinite Array.

A Bitonic array is an array which only contains 0’s and 1’s. You are provided with an infinite array which contains only 0’s and 1’s. You need to find first Occurance of 1 in this array.

Approach
Go through the approach of finding first Occurance discussed before and the Bitonic Array approach.

10. Searching in 2-D Array

Search An element in 2-D Matrix

Structure:

{10, 20, 30, 40},
{15, 25, 35, 96},
{17, 29, 37, 98},
{32, 33, 39, 50}

Largest element at bottom right and smallest at Top left.

Approach
Based on monotonicity of number in the array, we’ll design the conditions of the loop. We’ll start with (0, column) and move accordingly.

Code

Conclusion

We did it! If you followed along with me through this whole tutorial, you should have a really good feel for Binary Search now. To summarize, we have divided the article into two parts. The first part deal with the Explanation of Binary Search Algorithm and few hidden Capabilities of the same. The second part(this article) covers rest of the Hiddent Capabilies and variations of Binary Search Algorithm.

This article should have given you a good understanding of Binary Search. There is much more to learn and improve, but I hope you feel confident delving in and playing around with Binary Search variations by yourself now.

• View Gist on GitHub

Please let me know if anything was unclear, or if there’s anything else you’d like to see in this or a subsequent article. Feel free to reach out to me anytime if you want to discuss something. I would be more than happy if you send your feedback, suggestions.

Thanks a lot for reading till end. You can contact me in case if you need any assistance:

Web: https://portfolio.abhisheksrivastava.me/
Instagram: https://www.instagram.com/theprogrammedenthusiast/
LinkedIn: https://www.linkedin.com/in/abhishek-srivastava-49482a190/
Github: https://github.com/abhishek2x
Email: abhisheksrivastavabbn@gmail.com