A Binary Search Template
Introduction
Binary search is often used to efficiently locate an item in a sorted sequence of items. Compared to linear search which requires O(n) running time, binary search only takes O(log n) where n is the size of the sequence. Binary search is one of the most frequently asked type of problems in technical interviews. Many candidates struggle when the sequence of items contains duplicates.
Template
Below is a Python binary search template that works for duplicate items:
def search(nums, condition):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if condition(nums[mid]):
right = mid
else:
left = mid + 1
return left
The search function finds the index of the first item in nums that satisfies the condition. It takes two arguments: nums which is a list of items and condition which is a boolean function that returns True when the condition is met.
Usage
Here’s how we can implement the bisect_left function in Python’s bisect module.
def bisect_left(nums, target):
"""Locate the insertion point for target in nums to maintain sorted order."""
return search(nums, lambda x: x >= target)
The code for bisect_right is similar:
def bisect_right(nums, target):
"""Returns an insertion point which comes after any existing entries of target in nums."""
return search(nums, lambda x: x > target)
Armed with bisect_left and bisect_right, we can solve Leetcode 34. Find First and Last Position of Element in Sorted Array:
def search_range(nums, target):
"""
Given an array of integers nums sorted in ascending order,
find the starting and ending position of a given target value.
If the target is not found in the array, return (-1, -1).
"""
left = bisect_left(nums, target)
if left < len(nums) and nums[left] == target:
right = bisect_right(nums, target)
return (left, right - 1)
return (-1, -1)