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: Preimage Size of Factorial Zeroes FunctionLeetcode: Online ElectionLeetcode: Most Profit Assigning WorkLeetcode: Longest Repeating SubstringLeetcode: Koko Eating BananasLeetcode: 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: 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