Binary Search

Binary Search is an efficient algorithm used to find a target value within a sorted array. In each iteration, it halves the search space, achieving logarithmic time complexity ( $O (l o g (n))$ ).

Implementation

We can implement this algorithm both recursively and iteratively.

Iterative Binary Search

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

Recursive Binary Search

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def helper(low: int, high: int) -> int:
            if low > high:
                return -1

            mid = (low + high) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] < target:
                return helper(mid + 1, high)
            else:
                return helper(low, mid - 1)

        return helper(0, len(nums) - 1)

`bisect` module

In Python, we can use the bisect module to look for the insertion point (either left or right) in sorted lists.

These are the signatures of the two functions:

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)

Let's have a look at the following examples:

>>> import bisect

>>> l = [0, 0, 1, 1, 1, 2, 3, 4, 4]
>>> len(l)
9

# no values less than `-100`. Hence, it would be the first element of the list
>>> bisect.bisect_left(l, -100)
0

# smaller value is `0`. Hence, `0` goes first for `bisect_left`
>>> bisect.bisect_left(l, 0)
0
# smaller value is `0`, which is already at position `0` and `1`.
# Hence, the next `0` would go at position `2` for `bisect_right`
>>> bisect.bisect_right(l, 0)
2

# same considerations for the `0` for another existing element in the list
>>> bisect.bisect_left(l, 4)
7
>>> bisect.bisect_right(l, 4)
9
>>>

# no element bigger than `100`. Hence, it will be the new last element of the list
>>> bisect.bisect_right(l, 100)
9

Notice that in the examples above we always used 0 and len(l) as lower and upper bounds, respectively. However, we can also specify any other range.

Additional Usage

Binary Search works quite well on any sorted sequence. So let's now think of an ordered list of booleans:

l = [False, False, False, False, True, True]

It is easy to determine the first False value of the list, since it is ordered. However, what about the first True value?

Again, the list is ordered, which means that we can apply Binary Search:

from typing import List


def search(self, nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    first_true_idx = -1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid]:
            first_true_idx = mid
            right = mid - 1
        else:
            left = mid + 1

    return first_true_idx

first_true_idx will contain the index of the leftmost True value of the list.

How can we use such pattern?

Suppose that we have a monotonic increasing function:

def mon_inc_func(n):
    return n > 2

For the following input, the function will return an ordered output:

input = [0, 1, 2, 3, 4, 5, 6]
output = [mon_inc_func(i) for i in input]

print(output)
# [False, False, False, True, True, True, True]

Now, suppose that we do not know how this monotonic increasing function is implemented, so we do not know the source code of mon_inc_func. How can we use Binary Search to find the first value of the function that returns True?

We can use the previous snippet and simply replace nums[mid], which is looking for a True value, with the result of the function:

from typing import List


def unknown_function(n: int) -> bool:
    pass


def search(self, nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    first_true_idx = -1

    while left <= right:
        mid = (left + right) // 2

        if unknown_function(mid):  # instead of `nums[mid]`
            first_true_idx = mid
            right = mid - 1
        else:
            left = mid + 1

    return first_true_idx

Monotonic Function Example

Let's look at a real example, where we can apply this variation of Binary Search. We can use the First Bad Version problem.

algo-ds.com