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:
python 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.
python 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:
python 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:
python 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