Searching Notes - Page 2

Aggressive Cows: binary search the largest minimum distance between cows placed in stalls, with a greedy feasibility check, O(n log range).

Kth Smallest Element in a Sorted Matrix (LeetCode 378): binary search on value, counting elements <= mid in O(n log(range)).

Find K Closest Elements (LeetCode 658): binary search the best window start so the k-length window is closest to x, in O(log(n-k)+k).

Search a 2D Matrix II (LeetCode 240): staircase search from the top-right corner eliminates a row or column each step, in O(m+n).

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).