File BinarySearch.h

↰ Parent directory (ADS/search)

The binary search of section 1.2 in a sorted vector A[ 0 .

Definition (ADS/search/BinarySearch.h)

Detailed Description

. n - 1 ]: v is compared with the middle item A[ m ] of the part A[ i .. j ] still to examine, and the search goes on in A[ i .. m - 1 ] if v < A[ m ] and in A[ m + 1 .. j ] if v > A[ m ]; the part halves at each call, so that at most :math:` lfloor log_2 n rfloor + 1 ` calls are made, 2 comparisons each. The middle is computed as :math:` m = i + lfloor ( j - i ) / 2 rfloor , which unlike :math: lfloor ( i + j ) / 2 rfloor ` cannot overflow (the bug of Arrays.binarySearch of Java until 2003). The search may report each call (i, j, m) to a function, as the table of the example.

decisionTree() gives the decision tree of the search, the binary tree whose root is the middle item A[ m ] of the vector and whose subtrees are the decision trees of A[ 0 .. m - 1 ] and of A[ m + 1 .. n - 1 ]: a search for v is the path from the root down to the node of v, or to a missing child, so that its comparisons are the depth of that node plus one. Its invisit gives A, it is a binary search tree [see File SearchTree.h] and all its levels are full but the last one, hence its height is :math:` lfloor log_2 n rfloor `, the worst case of the search.

lowerBound() and upperBound() give the first place of an item not smaller, and larger, than v, with :math:` lceil log_2 ( n + 1 ) rceil ` comparisons: their difference is the number of occurrences of v (exercise 12.13). gallopSearch() looks for the first place of an item not smaller than v by doubling a bound before the binary search, in :math:` O( log h ) ` time if that place is h (exercise 12.9).

The contracts [see File Contract.h]: the vector must be sorted, an audit checked at the level 3 since it costs O( n ) against the O( log n ) of the search; lowerBound() also needs lo <= hi <= n, and the place it returns is checked against its two neighbours. The functions are defined in BinarySearch.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 1.2, https://algoritmicamente.it/materiali/libro/capitoli/cap01.pdf

    1. Bentley, A. C.-C. Yao, An almost optimal algorithm for unbounded searching, Information Processing Letters 5(3), 82-87, 1976, doi:10.1016/0020-0190(76)90071-5

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions