Review: Binary Search Problems Posted on January 22, 2018January 27, 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 Missing Element in Sorted Array LeetCode: Missing Element in Sorted Array 7 Find smallest letter greater than target LeetCode: Find Smallest Letter Greater Than Target 8 Random Point in Non-overlapping Rectangles LeetCode: Random Point in Non-overlapping Rectangles 9 Binary search on monotonic function LeetCode: Sqrt(x), LeetCode: Capacity To Ship Packages Within D Days 10 Place k elements to minimize max distance LeetCode: Minimize Max Distance to Gas Station 11 Kth Smallest Number in Multiplication Table LeetCode: Kth Smallest Number in Multiplication Table 12 Search for a Range Leecode: Search for a Range 13 Mountain Array LeetCode: Peak Index in a Mountain Array 14 Dynamic programming with binary search LeetCode: Maximum Profit in Job Scheduling 15 Montone stack with binary search LeetCode: Maximum Width Ramp 16 Find Right Interval Leecode: Find Right Interval 17 Patient sort LeetCode: Longest Increasing Subsequence 18 Find Minimum in Rotated Sorted Array LeetCode: Find Minimum in Rotated Sorted Array 19 Find Minimum in Rotated Sorted Array II LeetCode: Find Minimum in Rotated Sorted Array II 20 Maximum Profit in Job Scheduling Leetcode: Maximum Profit in Job Scheduling 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: Time Based Key-Value StoreLeetcode: Sqrt(x)Leetcode: Single Element in a Sorted ArrayLeetcode: Search Insert PositionLeetcode: Search in Rotated Sorted Array II See more blog posts. Post Views: 6