Review: Binary Search Problems Posted on January 22, 2018September 16, 2019 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 Questions 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? Scenarios Name Example Find whether target in the range Leetcode: Guess Number Higher or Lower Find the first target with duplicates Leetcode: First Bad Version Find the last target with duplicates Search insert position Leetcode: Search Insert Position Find smallest letter greater than target Leetcode: Find Smallest Letter Greater Than Target Leecode: Find Right Interval Leecode: Search for a Range Leecode: Sqrt(x) CheatSheet: Leetcode For Code Interview 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 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: Longest Repeating SubstringLeetcode: Longest Duplicate SubstringLeetcode: 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 Minimum in Rotated Sorted Array IILeetcode: Find Minimum in Rotated Sorted ArrayLeetcode: Find K-th Smallest Pair DistanceLeetcode: Find in Mountain ArrayLeetcode: 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