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

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.

😏 But did you just notice that there is a pitfall?

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 😉