Editing Binary search (section)

=== Uniform binary search ===
{{Main|Uniform binary search}}
[[File:Uniform binary search.svg|thumb|upright=1.0|[[Uniform binary search]] stores the difference between the current and the two next possible middle elements instead of specific bounds.]]
Uniform binary search stores, instead of the lower and upper bounds, the difference in the index of the middle element from the current iteration to the next iteration. A [[lookup table]] containing the differences is computed beforehand. For example, if the array to be searched is {{math|[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}}, the middle element (<math>m</math>) would be {{math|6}}. In this case, the middle element of the left subarray ({{math|[1, 2, 3, 4, 5]}}) is {{math|3}} and the middle element of the right subarray ({{math|[7, 8, 9, 10, 11]}}) is {{math|9}}. Uniform binary search would store the value of {{math|3}} as both indices differ from {{math|6}} by this same amount.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "An important variation"}} To reduce the search space, the algorithm either adds or subtracts this change from the index of the middle element. Uniform binary search may be faster on systems where it is inefficient to calculate the midpoint, such as on [[decimal computer]]s.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm U"}}