Binary Search: Usage

When do we use the binary search pattern?

Answer

As said before, We use binary search when the search space has a monotonic structure that lets us eliminate half of the search space at each iteration.

Common usages:

  • Search a target value or its index in a sorted array or matrix

    (Binary Search, Binary Search: Search 2D Matrix)

  • Search for a pivot point where an order breaks but each side remains sorted

    (Binary Search: Rotated Array, Binary Search: Finding Min in Rotated Array)

  • Insertion point so that array is sorted (can be lower or upper)

    (Binary Search: Slight Modification)

  • Search for a boundary (lower bound / upper bound)

    • first / last occurrence of target value

    • count of target values

  • Find the minimum or maximum feasible value (binary search over transformation)

    (Binary Search: Square Root of x, Koko Eating Bananas)

Back to collection