How to find the starting/ending position of an element using Binary Search

Sep 20, 2018 · 5 min read

Binary search is a fundamental algorithm in computer science. It looks easy(at first), but have you ever encountered these problems when you want to change a litter bit the algorithm to search for the boundaries…

You have no idea how to make it works…whats wrong?🤯

Before we go further, let’s do a warm-up with the most basic and elementary form of binary search.

• The `mean` is floored.
• The `arr[mean]` will be excluded in every next iteration.
• If the`target`doesn’t exist, the `min` and the`max` will be the same before the last iteration ends
• Therefore, the`min`is larger than the`max` if the `target` doesn’t exist.

Okay, I am ready to search for the boundaries now!!!

Let’s start searching for the lower bound,

According to the basic binary search, I expect my next iteration to be on the left-hand side,

so the logic should be:

If my target is smaller or equal to the middle item, the scope should be narrowed down to the left INCLUDING the middle item; else if my target is larger than the middle item, we should narrow down the scope to the right.

`if target <= arr[mean] {  max = mean} else {  min = mean + 1}`

You might be confused at some points, for instance:

1. Why can's we just compare if`target < arr[mean]` ?

It is because we need to include the boundary in the case that the `arr[mean]`is, one of the target, 3.

2. Why can’t `max = mean — 1` ?

If you do it, your scope will be narrowed down to just `1 2`eventually, that’s not what we want.

3. When should I end the loop?

I prefer to end my iteration when the `min` equals to the `max`, so both the `min`and the `max` point to the same item, it will be less ambiguous once it completes.

`while min < max {  ...}`

4. What if the target doesn’t exist in the array?

Good question!!! We need to do post-processing on returing the result; if the final item doesn’t equal to the target, we should return false or -1

`if arr[min] == target {  return min} else {  return -1}// note: it doesn't matter you use min or max. it is because min=max, read again the previous point if you don't know the reason`

And you come up with this !!!

🎉🎉🎉🎉Yeah! We just did the lower-bound binary search 🎉🎉🎉🎉

Let’s try to find the ending position of an element in the same way !!!

For comparison, we do it against the same array.

This time, we expect the right-hand side will be in the next iteration,

therefore the logic would be:

If my target is larger or equal to the middle item, my scope should be narrowed down to the right INCLUDING the middle item; else if my target is smaller than the middle item, narrow down the scope to the left.

`for min < max {  mean := (min + max) / 2  if target >= arr[mean] {    min = mean  } else {    max = mean - 1  }}`

The logic is similar to the lower-bound one, I guess you probably have even figured it out on you own.

Let’s take a look at the final iteration when the scope contains

If `mean := (min + max)/2`, the if-statement always compare the target with the first item, 3, it means the loop runs FOREVER !!!

Why?

Since the `min`always equals to `mean` when it proceeds to the next iteration, `max`is never be subtracted down to the number which equals to`min`. Hence, the loop condition, `for min < max`, is always true!!!!

So what should we do?

Actually, there are so many ways, the easiest way is to use the ceiling instead of the floor to compute the `mean`

`mean := (min + max + 1)/2// orlet mean = Math.ceil((min + max)/2)// or// ...`

Thereafter, we finally come up with this

🎉🎉🎉🎉 Great! 🎉🎉🎉🎉

Conclusion:

Let’s compare all the binary searches we have just done

There are several things we should focus on:

• The loop/iteration termination condition
• The `mean`calculation
• The comparison against the `target`
• When should we include the boundary
• And finally the post-processing

I hope it helps.

By the way, I am learning golang and I have just started my journey on a daily challenge, AlGoDaily. I have also included the above snippet in the same repo, please feel free to new an issue/pull-request on it. Thank you.

Edit: Thanks @hihanifm for the reminder, the upper-bound actually means the position of the “last index of the target”+1. e.g. 1233345, so the upper-bound should be 5(index of “4") instead of 4. I don’t want to edit the images again, forgive me 😉

Written by

Calvin Chan

Software Engineer @eBay, Gumtree AU

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just \$5/month. Upgrade