Understanding Binary Search

Binary search is a crucial technique for quickly locating elements, operating in O(log N) time. However, its subtleties can be challenging for many developers. By mastering bisect_left and bisect_right, programmers can tackle coding challenges with greater clarity and efficiency.

Consider this multiple-choice question:

Given the list [1, 3, 3, 3, 5, 7, 9], what will bisect_right([1, 3, 3, 3, 5, 7, 9], 3) yield?

1. 1
2. 2
3. 4
4. 5

The correct answer is C.

Now, let’s delve into the definitions of bisect_left() and bisect_right(). If you are already familiar with these concepts, feel free to skip ahead to the Smart Tricks section.

What is Binary Search?

The binary_search() function is designed to locate the index of a target value within a sorted array.

A = [2, 4, 4, 4, 6]

target = 6

# Result:

binary_search(A, target=6) # Returns: 4 # Found

binary_search(A, target=4) # Returns: 1 or 2 or 3 # Found

binary_search(A, target=-1) # Returns: -1 # Not found

binary_search(A, target=9) # Returns: -1 # Not found

It returns the index of the matched item; otherwise, it yields -1.

What is Bisect Left?

bisect_left() identifies the leftmost position for inserting an element while preserving order.

A = [2, 4, 4, 4, 6]

target = 6

# Result:

bisect.bisect_left(A, target=6) # Returns: 4 # Found

bisect.bisect_left(A, target=4) # Returns: 1 # Found

bisect.bisect_left(A, target=-1) # Returns: 0 # Not found

bisect.bisect_left(A, target=9) # Returns: 5 # Not found

Note that it will not return -1 for a miss; instead, it provides an insertion point. When the target matches, the result is identical to that of binary_search(), but it's essential to remember that the output from bisect_left() is solely an insertion point.

This insertion point can be utilized with insert() to add a new element while maintaining the sorted order:

insertion_point = bisect_left(A, target=4) # Returns: 1 # Found

A.insert(insertion_point, target=4)

# Result: A = [2, 4, 4, 4, 4, 6]

insertion_point = bisect_left(A, target=-99) # Returns: 0 # Not found

A.insert(insertion_point, target=-99)

# Result: A = [-99, 2, 4, 4, 4, 4, 6]

What is Bisect Right?

bisect_right() is employed to find the rightmost insertion point while maintaining the sorted order.

A = [2, 4, 4, 4, 6]

insertion_point = bisect_right(A, target=4) # Returns: 4 # Found

A.insert(insertion_point, target=4)

# Result: A = [2, 4, 4, 4, 4, 6]

Smart Tricks

1. Using `bisect_left()` to Implement `binary_search()`:

   Since bisect_left() returns the same result as binary_search() when the target matches, we can use it to create a binary search function.

import bisect

def my_binary_search(A, x):

pos = bisect.bisect_left(A, x)

if pos < len(A) and A[pos] == x:

return pos

else:

return -1

# Example usage

A = [1, 2, 4, 4, 5, 6, 8]

print(my_binary_search(A, 4)) # Output: 2

print(my_binary_search(A, 7)) # Output: -1

2. Using `bisect_left()` to Create `bisect_right()`:

   You can simulate bisect_right() by adding a small number (epsilon) to the target.

import bisect

epsilon = 1e-9

def my_bisect_right(A, x):

return bisect.bisect_left(A, x + epsilon)

# Example usage

A = [1, 2, 4, 4, 5, 6, 8]

print(my_bisect_right(A, 4)) # Output: 4

print(my_bisect_right(A, 3)) # Output: 2

3. Implementing `bisect_left()` and `bisect_right()` from Scratch:

   If using the bisect library is not allowed, you can write your own implementations.

def my_bisect_left(A, x):

lo, hi = 0, len(A)

while lo < hi:

mid = (lo + hi) // 2

if x <= A[mid]:

hi = mid

else:

lo = mid + 1

return lo

def my_bisect_right(A, x):

lo, hi = 0, len(A)

while lo < hi:

mid = (lo + hi) // 2

if x < A[mid]:

hi = mid

else:

lo = mid + 1

return lo

Effective Solutions with bisect_left() or bisect_right()

Problem 1: Find Right Interval

Given a list of intervals, find the smallest starting interval that comes after the end of each interval.

Input: intervals = [[3,4],[2,3],[1,2]]

Output: [-1,0,1]

Explanation: The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.

import bisect

def findRightInterval(intervals):

starts = sorted((e[0], i) for i, e in enumerate(intervals))

res = []

for interval in intervals:

pos = bisect.bisect_left(starts, (interval[1],))

res.append(starts[pos][1] if pos < len(starts) else -1)

return res

Problem 2: Longest Increasing Subsequence

To determine the length of the longest increasing subsequence in an array.

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]

Output: 4

import bisect

def lengthOfLIS(nums):

if not nums:

return 0

lis = []

for num in nums:

pos = bisect.bisect_left(lis, num)

if pos == len(lis):

lis.append(num)

else:

lis[pos] = num

return len(lis)