What is the time complexity of lower and upper bound?

Worst case O(log n). Space complexity is O(1). Same halving, with a half-open range so 'past the end' needs no special case.

Lower and upper bound

medium

Plain binary search finds *an* occurrence and cannot tell you how many there are. lowerBound and upperBound can - and their difference is the count, in O(log n).

Worst O(log n)Space O(1)

Loading the lower and upper bound engine…

Where to go next

Binary search

easy

Halve the search space with every comparison.

Binary search on the answer

hard

The interview version: search a predicate, not an array.

Longest increasing subsequence

medium

The O(n²) table, and the O(n log n) trick that replaces it.