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

### Further Exercises

## Related Posts

- Leetcode 424 - Longest Repeating Character Replacement
- Two Sum and Its Variants
- Single Number
- Leetcode 1004 - Max Consecutive Ones III
- Leetcode 222 - Count Complete Tree Nodes
- Leetcode 1027 - Longest Arithmetic Subsequence
- Question 1299 on leetcode
- Leetcode 240 - Search a 2D Matrix II
- Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
- Leetcode 239 - Sliding Window Maximum
- Leetcode 209 - Minimum Size Subarray Sum
- LeetCode 230 - Kth Smallest Element in a BST with Code
- advanced-applications-of-binary-search
- Leetcode 96 - Unique Binary Search Trees
- Leetcode 540 - Single Element in a Sorted Array
- Leetcode 1283 - Find the Smallest Divisor Given a Threshold
- Leetcode 74 - Search a 2D Matrix
- Leetcode 300 - Longest Increasing Subsequence
- Leetcode 930 - Binary Subarrays With Sum
- Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
- Leetcode 704 - Binary Search
- Leetcode 643 - Maximum Average Subarray I
- LeetCode - Two Sum Solution with Code
- Leetcode 1358 - Number of Substrings Containing All Three Characters
- Leetcode 33 - Search in Rotated Sorted Array
- Leetcode 1151 - Minimum Swaps to Group All 1’s Together