aarray + of integerand the linear search algorithm with sentinel is expressed by [ :xi : while [ix do inc(iend (adens _search *the resulting conditionderived from the same invariant as beforeis (ai (ak < ak xevidentlyi implies that no match (except that for the sentinelwas encountered binary search there is quite obviously no way to speed up searchunless more information is available about the searched data it is well known that search can be made much more effectiveif the data are ordered imaginefor examplea telephone directory in which the names were not alphabetically listed it would be utterly useless we shall therefore present an algorithm which makes use of the knowledge that is orderedi of the condition ak < ak- <ak the key idea is to inspect an element picked at randomsay amand to compare it with the search argument if it is equal to xthe search terminatesif it is less than xwe infer that all elements with indices less or equal to can be eliminated from further searchesand if it is greater than xall with index greater or equal to can be eliminated this results in the following algorithm called binary searchit uses two index variables and marking the left and at the right end of the section of in which an element may still be found : : - (adens _search * :any value between and rwhile ( < ( [mxdo if [mx then : + else : - endm :any value between and end note fundamental structural similarity of this algorithm and the linear search in the preceding sectionthe role of is now played by the triplet lmr to explicate the similarity andtherebyto better ensure the loop correctnesswe resisted the tempation of minor optimization that would eliminate one of the two identical assignments to the loop invarianti the condition satisfied before and after each stepis (ak xfrom which the result is derived as (( ror (am )(ak xwhich implies (( (ak < ak )or (am xthe choice of is apparently arbitrary in the sense that correctness does not depend on it but it does influence the algorithm' effectiveness clearly our goal must be to eliminate in each step as many elements