Binary search is important. The idea is simple.
But you wouldn’t believe how incredibly useful it would be.
Clarifications:
- Allow duplicate?
- What range you would choose to examine?
- How you can reduce the dataset into half?
Ideas
| Name | Example |
|---|---|
| Break case | for left+1<right: the same or adjacent |
| Break case | for left<right |
| Break case | for left<=right |
Where Left/Right Would Be After Search?
l = [2, 3, 8, 12, 20, 35], target = 4
- Found. Target = 3. left == right, points to the value
- In the middle. Target = 11. [right, Target, left]. The previous step would be right==left, and the value is smaller than the target. Do you know why?
- Too small. Target = 1. [right(-1), left(0)]
- Too big. Target = 36. [right(len-1), left(len)]
Scenarios:
| Name | Example |
|---|---|
| Find whether target in the range | Guess Number Higher or Lower |
| Find the first target | First Bad Version |
| Find smallest letter greater than target | Find Smallest Letter Greater Than Target |
| Search insert position |
The most impressive problems to me:
See all binarysearch problems: #binarysearch.
- Review: Binary Search Problems
- LintCode: Single Number IV
- LintCode: Leftmost One
- LintCode: Count Negative Number
- Leetcode: Valid Perfect Square
- Leetcode: Time Based Key-Value Store
- Leetcode: Sqrt(x)
- Leetcode: Single Element in a Sorted Array
- Leetcode: Search Insert Position
- Leetcode: Search in Rotated Sorted Array II
- Leetcode: Search in Rotated Sorted Array
- Leetcode: Search in a Sorted Array of Unknown Size
- Leetcode: Search for a Range
- Leetcode: Search a 2D Matrix II
- Leetcode: Search a 2D Matrix
- Leetcode: Preimage Size of Factorial Zeroes Function
- Leetcode: Most Profit Assigning Work
- Leetcode: Lowest Common Ancestor of a Binary Search Tree
- Leetcode: Longest Repeating Substring
- Leetcode: Guess Number Higher or Lower
- Leetcode: First Bad Version
- Leetcode: Find the Duplicate Number
- Leetcode: Find Smallest Letter Greater Than Target
- Leetcode: Find Minimum in Rotated Sorted Array II
- Leetcode: Find Minimum in Rotated Sorted Array
- Leetcode: Compare Strings by Frequency of the Smallest Character
- Leetcode: Closest Binary Search Tree Value
- Leetcode: Check If a Number Is Majority Element in a Sorted Array
- Leetcode: Binary Search
- Leetcode: Advantage Shuffle
See more blog_posts.
Share It, If You Like It.