Review: Binary Search Problems

Binary search is important. The idea is simple.

But you wouldn’t believe how incredibly useful it would be.

---

---

Basic Abstractions

Name	Summary
What are the arrays to be examined?
How to divide them into half?
Check the middle and how to drop one half?

Code Skeleton

Name	Example
Clarifications: whether array is sorted?
Clarifications: whether array allow duplicates?
How to initialize?	left, right := 0, len(l)-1 VS left, right := 0, len(l)
How to check, drop?	target -> middle vs middle -> target
How to move?	left = mid, left = mid+1, left = mid-1
When to break?	left<right: adjacent, left<=right: overlap
What break means?
Any corner case?

Top Questions

Num	Problem	Summary
1	Find whether target in the range	LeetCode: Guess Number Higher or Lower
2	Find the first target with duplicates	LeetCode: First Bad Version
3	Find the last target with duplicates	LeetCode: Longest Repeating Substring
4	Find the first and last target	LeetCode: Find First and Last Position of Element in Sorted Array
5	Search Insert Position	LeetCode: Search Insert Position, LeetCode: Time Based Key-Value Store
6	Mountain Array	LeetCode: Peak Index in a Mountain Array
7	Missing Element in Sorted Array	LeetCode: Missing Element in Sorted Array
8	Find smallest letter greater than target	LeetCode: Find Smallest Letter Greater Than Target
9	Random Point in Non-overlapping Rectangles	LeetCode: Random Point in Non-overlapping Rectangles
10	Binary search on monotonic function	LeetCode: Sqrt(x), LeetCode: Capacity To Ship Packages Within D Days
11	Place k elements to minimize max distance	LeetCode: Minimize Max Distance to Gas Station
12	Decide a number	LeetCode: Split Array Largest Sum
13	Kth Smallest Number in Multiplication Table	LeetCode: Kth Smallest Number in Multiplication Table
14	Search for a Range	Leecode: Search for a Range
15	Dynamic programming with binary search	LeetCode: Maximum Profit in Job Scheduling
16	Montone stack with binary search	LeetCode: Maximum Width Ramp
17	Find Right Interval	Leecode: Find Right Interval
18	Patient sort	LeetCode: Longest Increasing Subsequence
19	Find Minimum in Rotated Sorted Array	LeetCode: Find Minimum in Rotated Sorted Array
20	Find Minimum in Rotated Sorted Array II	LeetCode: Find Minimum in Rotated Sorted Array II
21	Maximum Profit in Job Scheduling	Leetcode: Maximum Profit in Job Scheduling
22	Tweet Counts Per Frequency	LeetCode: Tweet Counts Per Frequency
23	Median of Two Sorted Arrays	Leetcode: Median of Two Sorted Arrays

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups

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: Tweet Counts Per Frequency
• 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: Remove Interval
• LeetCode: Random Point in Non-overlapping Rectangles
• LeetCode: Random Pick with Weight
• LeetCode: Preimage Size of Factorial Zeroes Function
• LeetCode: Peak Index in a Mountain Array
• LeetCode: Online Election
• LeetCode: Most Profit Assigning Work
• LeetCode: Missing Element in Sorted Array
• LeetCode: Minimize Max Distance to Gas Station
• LeetCode: Maximum Width Ramp
• LeetCode: Maximum Profit in Job Scheduling
• LeetCode: Maximum Average Subarray II
• LeetCode: Majority Element II
• LeetCode: Longest Repeating Substring

See more blog posts.

---