Editing Binary search (section)

== Algorithm ==
Binary search works on sorted arrays. Binary search begins by comparing an element in the middle of the array with the target value. If the target value matches the element, its position in the array is returned. If the target value is less than the element, the search continues in the lower half of the array. If the target value is greater than the element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}

=== Procedure ===
Given an array <math>A</math> of <math>n</math> elements with values or [[Record (computer science)|records]] <math>A_0,A_1,A_2,\ldots,A_{n-1}</math>sorted such that <math>A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}</math>, and target value <math>T</math>, the following [[subroutine]] uses binary search to find the index of <math>T</math> in <math>A</math>.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}
# Set <math>L</math> to <math> 0</math> and <math>R</math> to <math>n-1</math>.
# If <math>L>R</math>, the search terminates as unsuccessful.
# Set <math>m</math> (the position of the middle element) to <math>L</math> plus the [[Floor and ceiling functions|floor]] of <math>\frac{R-L}{2}</math>, which is the greatest integer less than or equal to <math>\frac{R-L}{2}</math>.
# If <math>A_m < T</math>, set <math>L</math> to <math>m+1</math> and go to step 2.
# If <math>A_m > T</math>, set <math>R</math> to <math>m-1</math> and go to step 2.
# Now <math>A_m = T</math>, the search is done; return <math>m</math>.

This iterative procedure keeps track of the search boundaries with the two variables <math>L</math> and <math>R</math>. The procedure may be expressed in [[pseudocode]] as follows, where the variable names and types remain the same as above, <code>floor</code> is the [[floor function]], and <code>unsuccessful</code> refers to a specific value that conveys the failure of the search.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}
[[File:Binary-search-work.gif|thumb|right|binary-search]]
 '''function''' binary_search(A, n, T) '''is'''
     L := 0
     R := n &minus; 1
     '''while''' L ≤ R '''do'''
         m := L + floor((R - L) / 2)
         '''if''' A[m] < T '''then'''
             L := m + 1
         '''else if''' A[m] > T '''then'''
             R := m &minus; 1
         '''else''':
             '''return''' m
     '''return''' unsuccessful

Alternatively, the algorithm may take the [[Floor and ceiling functions|ceiling]] of <math>\frac{R-L}{2}</math>. This may change the result if the target value appears more than once in the array.

==== Alternative procedure ====
In the above procedure, the algorithm checks whether the middle element (<math>m</math>) is equal to the target (<math>T</math>) in every iteration. Some implementations leave out this check during each iteration. The algorithm would perform this check only when one element is left (when <math>L=R</math>). This results in a faster comparison loop, as one comparison is eliminated per iteration, while it requires only one more iteration on average.<ref name="Bottenbruch1962">{{cite journal|last1=Bottenbruch|first1=Hermann|s2cid=13406983|title=Structure and use of ALGOL 60|journal=[[Journal of the ACM]] |date=1 April 1962|volume=9|issue=2|pages=161–221 |issn=0004-5411|doi=10.1145/321119.321120 |doi-access=free}} Procedure is described at p. 214 (§43), titled "Program for Binary Search".</ref>

[[Hermann Bottenbruch]] published the first implementation to leave out this check in 1962.<ref name="Bottenbruch1962" />{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}

# Set <math>L</math> to <math> 0</math> and <math>R</math> to <math>n-1</math>.
# While <math>L \neq R</math>,
## Set <math>m</math> (the position of the middle element) to <math>L</math> plus the [[Floor and ceiling functions|ceiling]] of <math>\frac{R-L}{2}</math>, which is the least integer greater than or equal to <math>\frac{R-L}{2}</math>.
## If <math>A_m > T</math>, set <math>R</math> to <math>m-1</math>.
## Else, <math>A_m \leq T</math>; set <math>L</math> to <math>m</math>.
# Now <math>L=R</math>, the search is done. If <math>A_L=T</math>, return <math>L</math>. Otherwise, the search terminates as unsuccessful.

Where <code>ceil</code> is the ceiling function, the pseudocode for this version is:

 '''function''' binary_search_alternative(A, n, T) '''is'''
     L := 0
     R := n &minus; 1
     '''while''' L != R '''do'''
         m := L + ceil((R - L) / 2)
         '''if''' A[m] > T '''then'''
             R := m &minus; 1
         '''else''':
             L := m
     '''if''' A[L] = T '''then'''
         '''return''' L
     '''return''' unsuccessful

=== Duplicate elements ===
The procedure may return any index whose element is equal to the target value, even if there are duplicate elements in the array. For example, if the array to be searched was <math>[1,2,3,4,4,5,6,7]</math> and the target was <math>4</math>, then it would be correct for the algorithm to either return the 4th (index 3) or 5th (index 4) element. The regular procedure would return the 4th element (index 3) in this case. It does not always return the first duplicate (consider <math>[1,2,4,4,4,5,6,7]</math> which still returns the 4th element). However, it is sometimes necessary to find the leftmost element or the rightmost element for a target value that is duplicated in the array. In the above example, the 4th element is the leftmost element of the value 4, while the 5th element is the rightmost element of the value 4. The alternative procedure above will always return the index of the rightmost element if such an element exists.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}

==== Procedure for finding the leftmost element ====
To find the leftmost element, the following procedure can be used:{{Sfn|Kasahara|Morishita|2006|pp=8–9}}

# Set <math>L</math> to <math> 0</math> and <math>R</math> to <math>n</math>.
# While <math>L < R</math>,
## Set <math>m</math> (the position of the middle element) to <math>L</math> plus the [[Floor and ceiling functions|floor]] of <math>\frac{R-L}{2}</math>, which is the greatest integer less than or equal to <math>\frac{R-L}{2}</math>.
## If <math>A_m < T</math>, set <math>L</math> to <math>m+1</math>.
## Else, <math>A_m \geq T</math>; set ''<math>R</math>'' to <math>m</math>.
# Return <math>L</math>.

If <math>L < n</math> and <math>A_L = T</math>, then <math>A_L</math> is the leftmost element that equals <math>T</math>. Even if <math>T</math> is not in the array, <math>L</math> is the [[#Approximate matches|rank]] of <math>T</math> in the array, or the number of elements in the array that are less than <math>T</math>.

Where <code>floor</code> is the floor function, the pseudocode for this version is:

 '''function''' binary_search_leftmost(A, n, T):
     L := 0
     R := n
     '''while''' L < R:
         m := L + floor((R - L) / 2)
         '''if''' A[m] < T:
             L := m + 1
         '''else''':
             R := m
     '''return''' L

==== Procedure for finding the rightmost element ====
To find the rightmost element, the following procedure can be used:{{Sfn|Kasahara|Morishita|2006|pp=8–9}}

# Set <math>L</math> to <math> 0</math> and <math>R</math> to <math>n</math>.
# While <math>L < R</math>,
## Set <math>m</math> (the position of the middle element) to <math>L</math> plus the [[Floor and ceiling functions|floor]] of <math>\frac{R-L}{2}</math>, which is the greatest integer less than or equal to <math>\frac{R-L}{2}</math>.
## If <math>A_m > T</math>, set <math>R</math> to <math>m</math>.
## Else, <math>A_m \leq T</math>; set ''<math>L</math>'' to <math>m+1</math>.
# Return <math>R - 1</math>.

If <math>R > 0</math> and <math>A_{R-1}=T</math>, then <math>A_{R-1}</math> is the rightmost element that equals <math>T</math>. Even if ''<math>T</math>'' is not in the array, <math>n-R</math> is the number of elements in the array that are greater than ''<math>T</math>''.

Where <code>floor</code> is the floor function, the pseudocode for this version is:

 '''function''' binary_search_rightmost(A, n, T):
     L := 0
     R := n
     '''while''' L < R:
         m := L + floor((R - L) / 2)
         '''if''' A[m] > T:
             R := m
         '''else''':
             L := m + 1
     '''return''' R - 1

=== 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"}}