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