LeetCode 911: Online Election
A clear explanation of Online Election using preprocessing and binary search over vote times.
Tag
Binary-Search
91 notes
LeetCode 887: Super Egg Drop
A clear explanation of finding the minimum worst-case number of moves using dynamic programming over eggs and moves.
LeetCode 878: Nth Magical Number
A clear explanation of finding the nth magical number using binary search, greatest common divisor, least common multiple, and inclusion-exclusion.
LeetCode 981: Time Based Key-Value Store
A clear explanation of designing a time-based key-value store using a hash map and binary search.
LeetCode 875: Koko Eating Bananas
A clear explanation of finding the minimum banana-eating speed using binary search on the answer.
LeetCode 855: Exam Room
A clear explanation of simulating an exam room by maintaining occupied seats in sorted order.
LeetCode 852: Peak Index in a Mountain Array
A clear explanation of finding the peak index in a mountain array using binary search.
LeetCode 793: Preimage Size of Factorial Zeroes Function
A clear explanation of finding how many integers have exactly k trailing zeroes in their factorial.
LeetCode 774: Minimize Max Distance to Gas Station
A clear explanation of minimizing the largest adjacent gas-station distance using binary search on the answer.
LeetCode 719: Find K-th Smallest Pair Distance
A clear explanation of finding the kth smallest pair distance using sorting, binary search on the answer, and a two-pointer count.
LeetCode 715: Range Module
A clear explanation of designing a range module that can add, query, and remove half-open intervals.
LeetCode 704: Binary Search
A clear explanation of searching for a target in a sorted array using binary search.
LeetCode 702: Search in a Sorted Array of Unknown Size
A clear explanation of searching in a sorted array when the array length is hidden behind an ArrayReader interface.
LeetCode 744: Find Smallest Letter Greater Than Target
Use binary search to find the smallest character strictly greater than the target with wraparound handling.
LeetCode 668: Kth Smallest Number in Multiplication Table
A clear explanation of finding the kth smallest value in an m by n multiplication table using binary search on answer.
LeetCode 658: Find K Closest Elements
A clear explanation of finding the k closest elements to a target using binary search and a sliding window.
LeetCode 644: Maximum Average Subarray II
A binary search solution for finding the maximum average of any contiguous subarray with length at least k.
LeetCode 633: Sum of Square Numbers
A two-pointer and number theory solution for checking whether an integer can be written as the sum of two square numbers.
LeetCode 611: Valid Triangle Number
A two-pointer guide for counting triplets that can form valid triangles after sorting the side lengths.
LeetCode 240: Search a 2D Matrix II
A clear explanation of searching a row-sorted and column-sorted matrix using the top-right corner elimination method.
LeetCode 540: Single Element in a Sorted Array
A clear explanation of finding the only non-duplicate element in a sorted array using binary search.
LeetCode 528: Random Pick with Weight
A clear explanation of weighted random sampling using prefix sums and binary search.
LeetCode 497: Random Point in Non-overlapping Rectangles
A clear explanation of uniformly picking an integer point from non-overlapping rectangles using prefix sums and binary search.
LeetCode 483: Smallest Good Base
A clear explanation of finding the smallest base where n is written as all ones using geometric series and binary search.
LeetCode 475: Heaters
A clear explanation of finding the minimum heater radius by sorting positions and matching each house to its nearest heater.
LeetCode 441: Arranging Coins
Find the maximum number of complete staircase rows that can be formed using binary search and triangular numbers.
LeetCode 436: Find Right Interval
Find, for each interval, the interval with the smallest start point greater than or equal to its end point using sorting and binary search.
LeetCode 410: Split Array Largest Sum
A clear explanation of minimizing the largest subarray sum using binary search on the answer and greedy validation.
LeetCode 400: Nth Digit
A clear explanation of finding the nth digit in the infinite integer sequence using digit groups and arithmetic.
LeetCode 378: Kth Smallest Element in a Sorted Matrix
A clear explanation of finding the kth smallest value in a row-sorted and column-sorted matrix using binary search on values.
LeetCode 374: Guess Number Higher or Lower
A clear explanation of finding the picked number using binary search and the guess API.
LeetCode 367: Valid Perfect Square
A clear explanation of checking whether an integer is a perfect square using binary search without sqrt.
LeetCode 363: Max Sum of Rectangle No Larger Than K
A clear explanation of reducing a 2D rectangle problem to a 1D prefix-sum problem with binary search.
LeetCode 354: Russian Doll Envelopes
A clear explanation of solving Russian Doll Envelopes using sorting and longest increasing subsequence.
LeetCode 352: Data Stream as Disjoint Intervals
A clear explanation of maintaining disjoint sorted intervals from a stream using insertion and merging.
LeetCode 302: Smallest Rectangle Enclosing Black Pixels
A clear explanation of Smallest Rectangle Enclosing Black Pixels using binary search on rows and columns.
LeetCode 300: Longest Increasing Subsequence
A dynamic programming and patience sorting solution for finding the longest strictly increasing subsequence in an array.
LeetCode 285: Inorder Successor in BST
A binary-search-style solution for finding the smallest node greater than p in a binary search tree.
LeetCode 278: First Bad Version
A binary search solution for finding the first bad version while minimizing calls to the isBadVersion API.
LeetCode 275: H-Index II
A clear explanation of the H-Index II problem using binary search on a sorted citations array.
LeetCode 270: Closest Binary Search Tree Value
A clear explanation of the Closest Binary Search Tree Value problem using the BST property to walk toward the target.
LeetCode 222: Count Complete Tree Nodes
A clear explanation of counting nodes in a complete binary tree faster than visiting every node.
LeetCode 81: Search in Rotated Sorted Array II
A detailed guide to solving Search in Rotated Sorted Array II with modified binary search and duplicate handling.
LeetCode 167: Two Sum II - Input Array Is Sorted
A clear explanation of finding two numbers in a sorted array using two pointers and constant extra space.
LeetCode 162: Find Peak Element
A clear explanation of finding any peak element using binary search on the slope of the array.
LeetCode 154: Find Minimum in Rotated Sorted Array II
A clear explanation of finding the minimum element in a rotated sorted array that may contain duplicates.
LeetCode 153: Find Minimum in Rotated Sorted Array
A clear explanation of finding the minimum element in a rotated sorted array using binary search.
LeetCode 74: Search a 2D Matrix
A clear guide to searching a sorted 2D matrix using binary search over a virtual one-dimensional array.
LeetCode 69: Sqrt(x)
A clear guide to computing the integer square root using binary search without built-in exponent functions.
LeetCode 35: Search Insert Position
A clear explanation of finding the index of a target, or where it should be inserted, using binary search.
LeetCode 34: Find First and Last Position of Element in Sorted Array
A clear explanation of finding the first and last index of a target in a sorted array using two binary searches.
LeetCode 33: Search in Rotated Sorted Array
A clear explanation of searching a rotated sorted array in logarithmic time using modified binary search.
LeetCode 4: Median of Two Sorted Arrays
A detailed explanation of finding the median of two sorted arrays using binary search over partitions.
Interpolation Search with Fallback
Use interpolation to estimate the target position, with binary search fallback when estimates become unreliable.
Cache Aware Binary Search
Arrange and search sorted data with explicit knowledge of cache lines or memory blocks.
Van Emde Boas Layout Search
Search a binary tree stored in recursive cache oblivious layout to reduce memory transfers.
Eytzinger Layout Search
Binary search over an array arranged in heap order to improve cache locality and branch predictability.
Branchless Binary Search
Perform binary search with conditional moves or arithmetic updates instead of unpredictable branches.
Kth Smallest Subarray Sum
Find the k-th smallest sum among all contiguous subarrays, usually for nonnegative arrays.
Kth Smallest Pair Distance
Find the k-th smallest absolute difference among all pairs in an array.
Selection in Sorted Matrix
Select the k-th smallest element from a matrix whose rows and columns are sorted.
Parallel Binary Search with DSU
Answer offline connectivity queries by combining parallel binary search with a disjoint set union.
2. Binary Search and Ordered Search
Binary search and its ordered-search relatives: interpolation, Fibonacci, rotated-array, matrix, parametric, and offline variants.
SIMD Binary Search
Use vector instructions to evaluate multiple candidate positions in a binary search step.
Branchless Lower Bound
Compute lower bound using arithmetic or conditional moves instead of branches.
Binary Insertion Sort
Insertion sort that uses binary search to find the insertion position, reducing comparisons.
Kth Smallest Fraction
Select the k-th smallest fraction formed by pairs from a sorted array using heap or binary search.
Kth Smallest in Two Sorted Arrays
Select the k-th smallest element from two sorted arrays without merging them.
Binary Search
Search a sorted array by repeatedly halving the search interval.
Last True Binary Search
Find the last position where a monotone predicate remains true.
Equal Range Search
Find the range of indices containing all occurrences of a value in a sorted array.
Upper Bound
Find the first index where elements become strictly greater than a given value.
Integer Square Root by Binary Search
Compute the floor of the square root of a nonnegative integer using binary search.
Monotone Predicate Search
Find the boundary where a Boolean predicate changes value over an ordered domain.
Bisection Method
Find a root of a continuous function by repeatedly halving an interval where the function changes sign.
Offline Binary Search
Answer many monotone queries by processing them together after all input is known.
Parallel Binary Search
Answer many offline queries by searching their answers simultaneously with shared checks.
Powers of Two Search
Search for a boundary by trying decreasing jumps whose lengths are powers of two.
Fractional Cascading Search
Speed up repeated binary searches across related sorted lists by linking sampled elements between lists.
Matrix Binary Search
Search a row-major sorted matrix by treating it as a virtual sorted array.
One Dimensional Peak Finding
Find an element that is at least as large as its immediate neighbors.
Bitonic Array Search
Search a value in an array that first increases and then decreases.
Rotated Array Minimum Search
Find the smallest element in a sorted array that has been rotated around an unknown pivot.
Rotated Array Search
Search a value in a sorted array that has been rotated around an unknown pivot.
Uniform Binary Search
Binary search variant that uses precomputed step sizes instead of dynamic midpoint calculation.
Exponential Search
Locate a search interval by exponential growth, then apply binary search.
Binary Search on Answer
Find an optimal value by binary searching a monotone feasibility condition.
First True Binary Search
Find the first position where a monotone predicate becomes true.
Lower Bound
Find the first position where a value can be inserted without violating sorted order.
Recursive Binary Search
Binary search implemented using recursion over a shrinking interval.
Iterative Binary Search
Binary search implemented using a loop without recursion.