# 3 Simple Steps to Understand Binary Search - How to deal with when there is no exact match

##### May 04, 2020
``````    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 `=`.