# 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:

- 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

// 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
`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 😉