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:


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.


The code for bisect_right
is similar:


Armed with bisect_left
and bisect_right
, we can solve Leetcode 34. Find First and Last Position of Element in Sorted Array:

