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 ().
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.