# 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)
```