File SortedSearches.h

↰ Parent directory (ADS/search)

Searches in sorted vectors beyond the place of a given item [see File BinarySearch.h]: the minimum of a rotated vector, the item closest to a value, two items with a given sum, and the item of a given rank in the union of two sorted vectors, whose middle ranks are the medians.

Definition (ADS/search/SortedSearches.h)

Detailed Description

  • rotatedMinimum(): the place of the minimum of a strictly increasing vector rotated by an unknown number of places, which is that number; the minimum is in the right part of A[ lo .. hi ] if A[ m ] > A[ hi ], since then the rotation point is after m, and in A[ lo .. m ] otherwise; :math:` lceil log_2 n rceil ` comparisons. With repeated items no search can beat :math:` Omega( n ) ` comparisons in the worst case, as a vector of equal items but one shows, hence the items must be distinct;

  • closestValue(): the place of an item at the least distance from x, the smaller one on ties, and its first place among equal items; the first item not smaller than x [see lowerBound()] and the one before it are the only candidates, :math:` O( log n ) `. The distances are computed on the unsigned type of the same width for the integers, which cannot overflow; the test that compares | A[ m ] - x | with | A[ m + 1 ] - x | and goes right on ties misses a closer item on the left of a run of equal items, as 0 in [ 0 , 3 , 3 ] for x = 1;

  • pairWithSum(): two places i < j with A[ i ] + A[ j ] = x, by two indices from the ends, the left one moving right when the sum is too small and the right one moving left otherwise; each step excludes all the pairs of the item left behind, :math:` O( n ) ` against the :math:` O( n log n ) ` of a binary search for each item; a hash table does the same in :math:` O( n ) ` expected time on a vector that is not sorted. The sum is computed in the type of x, so that the items may be summed in a wider type;

  • kthOfTwoSorted(): the item of rank k (from 0) of the multiset union of the sorted X and Y, by a binary search of the number i of items taken from the shorter vector among the k + 1 smallest, j = k + 1 - i being taken from the other one: i is right when :math:` X[ i - 1 ] le Y[ j ] ` and :math:` Y[ j - 1 ] le X[ i ] ; :math: O( log min( m , n ) ) ` comparisons, against the :math:` O( k ) ` of a merge. The two medians of two sorted vectors of n items are the items of ranks n - 1 and n.

The contracts [see File Contract.h]: the vectors must be sorted, rotatedMinimum() needs a rotation of a strictly increasing vector, all audits checked at the level 3 since they cost O( n ); closestValue() and rotatedMinimum() need a vector that is not empty, kthOfTwoSorted() a rank k < m + n, and their results are checked against a scan of the vector, an audit. The functions are defined in SortedSearches.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 1.2 and Esercizi Divide-et-impera, Raccolte da compiti scritti

    1. Frederickson, D. B. Johnson, The complexity of selection and ranking in X + Y and matrices with sorted columns, Journal of Computer and System Sciences 24(2), 197-208, 1982, doi:10.1016/0022-0000(82)90048-4

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions