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

Calvin Chan
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 thetargetdoesn’t exist, the min and themax will be the same before the last iteration ends
  • Therefore, theminis larger than themax 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 iftarget < 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 2eventually, 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 minand 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 minalways equals to mean when it proceeds to the next iteration, maxis never be subtracted down to the number which equals tomin. 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// or
let 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 meancalculation
  • 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 😉

Calvin Chan

Written by

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