Data Structures Notes - Page 4

Search a 2D Matrix (LeetCode 74): treat the row-sorted matrix as one sorted list and binary search in O(log(m*n)).

Median of Two Sorted Arrays (LeetCode 4): binary search a partition of the smaller array for O(log(min(m,n))) time.

Split Array Largest Sum (LeetCode 410): binary search the largest subarray sum with a greedy split check, O(n log sum).

Capacity To Ship Packages Within D Days (LeetCode 1011): binary search the ship capacity with a greedy feasibility check, O(n log sum).

Koko Eating Bananas (LeetCode 875): binary search on the eating speed, checking feasibility in O(n log maxPile).

Compute integer Sqrt(x) (LeetCode 69) with binary search on the answer in O(log x), rounding down, in Python, Java and C++.

Find Peak Element (LeetCode 162): binary search on the slope to find any element greater than its neighbours in O(log n).

Find Minimum in Rotated Sorted Array (LeetCode 153): binary search comparing mid with the right end, in O(log n).

Search in Rotated Sorted Array II (LeetCode 81) with duplicates: binary search that shrinks ambiguous ends, O(log n) average and O(n) worst case.

Search in Rotated Sorted Array (LeetCode 33): modified binary search that identifies the sorted half each step, in O(log n).

Find First and Last Position of a target in a sorted array (LeetCode 34) using two binary searches (lower and upper bound) in O(log n).

Search Insert Position (LeetCode 35): use lower-bound binary search to find where a target is or should be inserted, in O(log n).