How to find array elements that fall in a given interval?
algorithm, arrays
Solution
One option would be to preprocess the array by sorting it into ascending order. Once you've done that, you can find all elements that fall within an interval by doing two binary searches over the sorted array - one to find the first element greater than or equal to the start of the interval and one to find the last element no greater than the endpoint of the interval - and then iterate across the array to output all elements in that range.
This requires O(n log n) time to preprocess if you use a standard sorting algorithm like quicksort or heapsort, but can be done in O(n log U) time if you use radix sort (here, U is the largest integer in the range). Queries then take time O(log n + k) each, where n is the number of elements and k is the number of elements within the range.
If you want to get fancy, you can speed this up exponentially by using a van Emde Boas tree, a specialized data structure for storing integers. If the largest integer value you are working with is U, then you can build the structure in time O(n log log U) and then do the endpoint range searches in time O(log log U). You can then find all elements in the range in time O(log log U) apiece, giving an O(k log log U) algorithm for finding all matches within a range.
Hope this helps!
Problem
This is an interview question. Given an array of integers and a stream of intervals (pairs of integers) find the elements of the array that fall in each interval of the stream. What array pre-processing would you use?