# A Binary Search Template

☰ Table of Content

### 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:

 ``````1 2 3 4 5 6 7 8 9 `````` ``````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.

 ``````1 2 3 `````` ``````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:

 ``````1 2 3 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````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) ``````

### Further Exercises

Update: 2021-10-19