Searching & Binary Search Notes

Classic iterative binary search on a sorted array in O(log n) time, with Python, Java and C++ code and an overflow-safe midpoint.

Recursive binary search on a sorted array in O(log n) time with O(log n) call-stack space, in Python, Java and C++.

Search Insert Position (LeetCode 35): use lower-bound binary search to find where a target is or should be inserted, 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 in Rotated Sorted Array (LeetCode 33): modified binary search that identifies the sorted half each step, 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.

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

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

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

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

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

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