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

    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 =.