sorted list

A list kept in ascending order, which supports O(log n) search with binary search at the cost of O(n) insertion.

In more detail

A sorted list can answer range queries, such as "all values between 10 and 20", which a hash-based set cannot. Inserting in the middle shifts elements, so it suits data that is read far more often than it changes. Balanced trees give fast search and fast insertion together.

Related terms

Taught in

References