Review: Binary Search Problems Posted on January 22, 2018July 26, 2020 by braindenny 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 ProblemsLintCode: Single Number IVLintCode: Leftmost OneLintCode: Count Negative NumberLeetCode: Valid Perfect SquareLeetCode: Tweet Counts Per FrequencyLeetCode: Time Based Key-Value StoreLeetCode: Sqrt(x)LeetCode: Single Element in a Sorted ArrayLeetCode: Search Insert PositionLeetCode: Search in Rotated Sorted Array IILeetCode: Search in Rotated Sorted ArrayLeetCode: Search in a Sorted Array of Unknown SizeLeetCode: Search for a RangeLeetCode: Search a 2D Matrix IILeetCode: Search a 2D MatrixLeetCode: Remove IntervalLeetCode: Random Point in Non-overlapping RectanglesLeetCode: Random Pick with WeightLeetCode: Preimage Size of Factorial Zeroes FunctionLeetCode: Peak Index in a Mountain ArrayLeetCode: Online ElectionLeetCode: Most Profit Assigning WorkLeetCode: Missing Element in Sorted ArrayLeetCode: Minimize Max Distance to Gas StationLeetCode: Maximum Width RampLeetCode: Maximum Profit in Job SchedulingLeetCode: Maximum Average Subarray IILeetCode: Majority Element IILeetCode: Longest Repeating SubstringLeetCode: Longest Duplicate SubstringLeetCode: Leftmost Column with at Least a OneLeetCode: Kth Smallest Number in Multiplication TableLeetCode: Koko Eating BananasLeetCode: K-th Smallest Prime FractionLeetCode: H-Index IILeetCode: Guess Number Higher or LowerLeetCode: First Bad VersionLeetCode: Find the Duplicate NumberLeetCode: Find Smallest Letter Greater Than TargetLeetCode: Find Peak ElementLeetCode: Find Minimum in Rotated Sorted Array IILeetCode: Find Minimum in Rotated Sorted ArrayLeetCode: Find K-th Smallest Pair DistanceLeetCode: Find in Mountain ArrayLeetCode: Find First and Last Position of Element in Sorted ArrayLeetCode: Exam RoomLeetCode: Compare Strings by Frequency of the Smallest CharacterLeetCode: Closest Binary Search Tree ValueLeetCode: Check If a Number Is Majority Element in a Sorted ArrayLeetCode: Capacity To Ship Packages Within D DaysLeetCode: Binary SearchLeetCode: Advantage Shuffle See more blog posts. Post Views: 6