A Binary Search Template
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.
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
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.
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)
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)