Binary Search

In a sorted array, compare the target with the middle element and throw away the half that cannot contain it, so you find any value in O(log n) steps.

Lower bound finds the first index whose value is >= target and upper bound finds the first index whose value is > target, which gives first and last positions, counts and insert points in O(log n).

A rotated sorted array is two sorted runs glued together; at every mid point at least one half is still sorted, so you can check that half and keep binary searching in O(log n).

When you can quickly check whether a candidate answer is good enough, and goodness only flips once as the candidate grows, binary search over the range of possible answers instead of over an array.

If the whole matrix reads as one sorted list row by row, binary search it as a flat array in O(log(m x n)); if only rows and columns are each sorted, walk a staircase from a corner in O(m + n).