On Searching an Approximately Sorted Array

Abstract Range search is a crucial problem in computer science, particularly in database systems. Existing algorithms for multidimensional range searches typically rely on fully sorted data or multidimensional range trees. We address the scenario in which the input is approximately sorted across dimensions. We define three metrics to measure the disorder in an approximately sorted array: number of inversions ({ inv}), maximum displacement ({ md}), and maximum distance ({ dis}). Our goal is to develop range search algorithms that are tailored to arrays that satisfy these disorder metrics. For the 1D range search, given { md} or { dis}, we achieve a search with comparisons log₂ n/4L + 10L + k, where n is the number of elements, L is the disorder metric and k is the output size. We extend this to catalog search using fractional cascading across approximately sorted K catalogs, requiring log₂ m/4L + 1 + 4KL + k comparisons, where m is the length of the first catalog. For 2D range search on approximately sorted coordinates, we need 5 log₂ m/4L + 4L(2 + 3K) + k + 3 comparisons. This method is generalized to multidimensional range searches on d-dimensional data with (2 log₂ n/4L + 8L + 2)ᵈ⁻¹ + 3(log₂ n/4L + 4KL + k + 1) comparisons. These techniques are particularly beneficial in database management and big data applications, where maintaining exact order is costly and real-time performance is critical.