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
- bisect module — Python's standard-library module of correct binary-search functions for sorted lists.
- range query — A request for every item whose key lies between two bounds, such as all orders placed between 9:00 and 10:00.
- set — Python's built-in unordered collection of unique items, implemented as a hash table that stores keys without values.
- balanced tree — A tree kept close to its minimum possible height, O(log n), so that searches never take long paths.
Taught in
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers
- Binary Search And Its Invariant — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers