Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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 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
  • LeetCode: Longest Duplicate Substring
  • LeetCode: Leftmost Column with at Least a One
  • LeetCode: Kth Smallest Number in Multiplication Table
  • LeetCode: Koko Eating Bananas
  • LeetCode: K-th Smallest Prime Fraction
  • LeetCode: H-Index II
  • LeetCode: Guess Number Higher or Lower
  • LeetCode: First Bad Version
  • LeetCode: Find the Duplicate Number
  • LeetCode: Find Smallest Letter Greater Than Target
  • LeetCode: Find Peak Element
  • LeetCode: Find Minimum in Rotated Sorted Array II
  • LeetCode: Find Minimum in Rotated Sorted Array
  • LeetCode: Find K-th Smallest Pair Distance
  • LeetCode: Find in Mountain Array
  • LeetCode: Find First and Last Position of Element in Sorted Array
  • LeetCode: Exam Room
  • LeetCode: Compare Strings by Frequency of the Smallest Character
  • LeetCode: Closest Binary Search Tree Value
  • LeetCode: Check If a Number Is Majority Element in a Sorted Array
  • LeetCode: Capacity To Ship Packages Within D Days
  • LeetCode: Binary Search
  • LeetCode: Advantage Shuffle

See more blog posts.

linkedin
github
slack

Post Views: 6
Posted in ReviewTagged binarysearch, review

Post navigation

LeetCode: Flatten Nested List Iterator
Review: Binary Tree Problems

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.