```
def bs(self, x, values):
left, right = 0, len(values)-1
while left < right:
mid = math.ceil((left+right)/2)
if values[mid] > x:
right = mid - 1
else:
left = mid
return left
```

Binary search is one of the most frequently used algorithms. To find an exact match is pretty straightforward. But what if **there's no exact match in the array**? That's when it gets a bit complicated.

Although it's not that difficult to figure out, your whole interview may depend on small details like this. An extra 5 minutes spent on getting it to work during an interview may cost you an offer.

So in this article, you will learn 3 steps that can help you understand binary search and be able to use it in any situation.

## ceil or floor？

Consider this line `mid = math.ceil((left+right)/2)`

. How do you determine when to use `ceil((left+right)/2)`

and when to use `(left+right)//2`

?

Let's look at an example: Lets say in an array`[1, 3]`

, we want to search for `2`

If we use ceil, `mid`

will be the second element, `3`

, in which case because 3 is larger than our target 2, the right pointer will be moved left, so we will get `1`

(whose index is 0) as a result. If we use floor, `mid`

will be the first element, `1`

, so we will get 3(at index 1) as a result.

So ultimately it boils down to whether you want a number larger than the target, or a number smaller than the target when there is no exact match.

**If you want a number greater than the target, use floor. If you want a number smaller than the target, use ceil.**

If you still find it confusing, experimenting with the code below might clear up things a little bit.

```
from typing import List
import math
def bs(nums: List, x: int):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == x:
return mid
elif nums[mid] > x:
right = mid
else:
left = mid + 1
return left, right
def bs2(nums: List, x: int):
left, right = 0, len(nums)
while left < right:
mid = math.ceil((left+right)/2)
if nums[mid] == x:
return mid
elif nums[mid] > x:
right = mid-1
else:
left = mid
return left, right
def test1():
nums = [1, 2, 3, 4, 7, 8, 9]
x = 6
print(bs(nums, x))
print(bs2(nums, x))
test1()
```

`mid+1`

or `mid-1`

or `mid`

?

When narrowing down the range, we can either move the left and right boundaries with

```
left = mid+1
right = mid
```

or we can also use

```
left = mid
right = mid-1
```

How do we determine when to use which? It actually depends on the first step.

Lets look at the same case again: `[1, 3]`

If we chose to use ceil in the last step, `mid`

will be the second element, `3`

, meaning `mid`

is already equal to `right`

. In this case, `right = mid`

doesn't change anything, leaving the range unchanged and causing an infinite loop.

This means **with ceil, we have to use**

```
left = mid
right = mid-1
```

and with **floor, we have to use**

```
left = mid+1
right = mid
```

`>=`

or `<=`

In the example code, I used `if values[mid] > x:`

, but why not use `>=`

? How do you determine when to use `>=`

or `>`

or `<=`

or `<`

?

It's simple. Just consider this case: `values=[5, 5, 5, 5, 5], x=5`

Which `5`

do you want returned in the array? If you want the rightmost one, that means you want to continue to move the range towards right even when `values[mid]`

is already equal to `x`

, meaning the `=`

should be in the condition for moving right. In this case, the statement is `left = mid`

. This is why for `right = mid - 1`

, I used `>`

without adding `=`

.