Editing Binary search (section)

=== Approximate matches ===
[[File:Approximate-binary-search.svg|thumb|upright=1.5|Binary search can be adapted to compute approximate matches. In the example above, the rank, predecessor, successor, and nearest neighbor are shown for the target value <math>5</math>, which is not in the array.]]
The above procedure only performs ''exact'' matches, finding the position of a target value. However, it is trivial to extend binary search to perform approximate matches because binary search operates on sorted arrays. For example, binary search can be used to compute, for a given value, its rank (the number of smaller elements), predecessor (next-smallest element), successor (next-largest element), and [[Nearest neighbor search|nearest neighbor]]. [[Range query (data structures)|Range queries]] seeking the number of elements between two values can be performed with two rank queries.{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Rank and selection"}}
* Rank queries can be performed with the [[#Procedure for finding the leftmost element|procedure for finding the leftmost element]]. The number of elements ''less than'' the target value is returned by the procedure.{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Rank and selection"}}
* Predecessor queries can be performed with rank queries. If the rank of the target value is <math>r</math>, its predecessor is&nbsp;<math>r-1</math>.{{Sfn|Goldman|Goldman|2008|pp=461–463}}
* For successor queries, the [[#Procedure for finding the rightmost element|procedure for finding the rightmost element]] can be used. If the result of running the procedure for the target value is ''<math>r</math>'', then the successor of the target value is&nbsp;<math>r+1</math>.{{Sfn|Goldman|Goldman|2008|pp=461–463}}
* The nearest neighbor of the target value is either its predecessor or successor, whichever is closer.
* Range queries are also straightforward.{{Sfn|Goldman|Goldman|2008|pp=461–463}} Once the ranks of the two values are known, the number of elements greater than or equal to the first value and less than the second is the difference of the two ranks. This count can be adjusted up or down by one according to whether the endpoints of the range should be considered to be part of the range and whether the array contains entries matching those endpoints.{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Range queries"}}