Find the first occurrence of a number using binary search

In this post we will take a look at a small modification to binary search. Instead of looking for the location of a specific target we will now try to find the first occurrence of that target.

For example if we have an array like below

and our target is 2 then out our answer solution should return 1 because 2 first occurs at the index of 1.

Just like in our previous post lets start off by identifying all those annoying edge cases so we can be aware of them when we start coding our solution. I’ve listed all the ones I can think of below.

Essentially I check cases where the target isn’t found, where it’s found on the edges, and I make sure the first occurrence of the target is found as well(this is the whole point of the algorithm). Now that I have all of these edge cases laid out and I am aware of them I can start to code a solution that takes all these situations into account. The last thing you want to do is get 80% done with an algorithm in an interview and start to realize that you haven’t addressed multiple edge cases. Then you end up trying to refactor your code and your solution becomes complicated and verbose.

My solution is below

So lets break down the differences in this solution and from my previous solution. Instead of returning a solution when I find a specific target in the array I just let the algorithm “collapse” on the target. So we just keep searching until we no longer can basically. This is done with this if statement

Another part of the solution that I would like to point out is the if statement before the for loop.

The ordering of the conditions here is critical. This is sometimes called short circuiting an if statement. We basically check to see if the our left pointer has left the bounds of the array. We know this is a possibility because we set it to l=mid+1. If we don’t check for this then we will get out of bounds errors in the cases where our target doesn’t exist in the array because its bigger than all the numbers in the array.

Well that does it for this binary search algorithm. In my next binary search post we will approach another problem that uses binary search but doesn’t involve arrays. Its important to get comfortable with the fact that binary search can be applied in a variety of situations.

Add a Comment

Your email address will not be published. Required fields are marked *