File KnuthSearches.h

↰ Parent directory (ADS/search)

Two searches of a sorted vector from Knuth, beyond the book [see File BinarySearch.h for the binary search of section 1.2]:

Definition (ADS/search/KnuthSearches.h)

Detailed Description

  • fibonacciSearch() (Algorithm 6.2.1F) splits the part still to examine at a Fibonacci number instead of the middle, so that the next part is found by subtractions alone, with no division: the part has length :math:` F_{k+1} - 1 , the item compared is the :math: F_k -th, and the two parts left have lengths :math: F_k - 1 ` and :math:` F_{k-1} - 1 ; at most about :math: 1.44 log_2 n ` comparisons, a little more than the binary search, for an average cost per step that was lower on the machines of the time (and may still be, where division is dear);

  • uniformBinarySearch() (Algorithm 6.2.1U, with the table of Algorithm C) keeps the place i of the last item compared and the width :math:` delta_j ` of the step j, :math:` delta_j = lfloor ( n + 2^{j-1} ) / 2^j rfloor `, precomputed: a step adds or subtracts the next width, so that the search moves on a fixed tree of differences with no endpoint to update.

Both return the place of v, or -1; when n is not a Fibonacci number, a probe of the Fibonacci search past the end of the vector is moved to its last item, which is the same as imagining items larger than all the others up to the next Fibonacci number; the uniform search may step to the places 0 and n + 1, which stand for the keys :math:` - infty ` and :math:` + infty ` of the book and are compared without reading the vector. The contracts [see File Contract.h]: the vector is sorted (an audit), and the result is -1 if and only if v is not there. The functions are defined in KnuthSearches.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 6.2.1

    1. Ferguson, Fibonaccian searching, Communications of the ACM 3(12), 648, 1960, doi:10.1145/367487.367496

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions