Range Search

This is the notes from what I learned in CS240. Similar notes are in Range Query.

Range searches in existing dictionary realizations:

• Unsorted list/array/hash table: Range search requires $\Omega (n)$ time: We have to check for each item explicitly whether it is in the range.
• Sorted array: Range search in A can be done in $O(\log n+s)$ time with Binary Search, where $s$ is the output size
• BST: Range searches can similarly be done in time $O(height+s)$ time, see BST Range Search.

Data Structures

• Quadtree
• kd-Tree
• Range Tree