Binary-Search

LeetCode 81 note: with duplicates, nums[l] == nums[mid] hides which half is sorted, so just move l right by one; worst case O(n)

LeetCode 74 note: each row continues the previous one in sorted order, so binary search it as a 1-D array of length m × n, mapping mid to (mid // n, mid % n)

LeetCode 34 note: two lower bounds: the first position >= target, and the first position >= target + 1 minus one

LeetCode 33 note: after rotation one side of mid is always sorted; check whether the target lies in it and search there, otherwise search the other side

LeetCode 888 note: equal sums after swapping x and y means y = x + (sumB - sumA) / 2; put B in a set and check each x from A

LeetCode 744 note: find the first letter > target (an upper bound), wrapping around to the first letter if none exists

LeetCode 704 note: a closed interval [l, r] with an integer mid; return on a match, otherwise discard the half that cannot contain the target

LeetCode 441 note: find the largest k with k(k + 1) / 2 <= n; when moving right write l = mid + 1 or the search gets stuck

LeetCode 374 note: adjust the range by guess’s result, where -1 means the guess is too high and 1 too low

LeetCode 367 note: binary search [1, num] for mid² == num without using sqrt

LeetCode 350 note: an intersection keeping multiplicity, where Counter’s & takes the smaller count from each side

LeetCode 349 note: convert both arrays to sets and intersect them