Editing Binary search (section)

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