Editing Binary search (section)

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