as possible from further searchesno matter what the outcome of the comparison is the optimal solution is to choose the middle elementbecause this eliminates half of the array in any case as resultthe maximum number of steps is log nrounded up to the nearest integer hencethis algorithm offers drastic improvement over linear searchwhere the expected number of comparisons is / the efficiency can be somewhat improved by interchanging the two if-clauses equality should be tested secondbecause it occurs only once and causes termination but more relevant is the questionwhether -as in the case of linear search - solution could be found that allows simpler condition for termination we indeed find such faster algorithmif we abandon the naive wish to terminate the search as soon as match is established this seems unwise at first glancebut on closer inspection we realize that the gain in efficiency at every step is greater than the loss incurred in comparing few extra elements remember that the number of steps is at most log the faster solution is based on the following invariant(ak xand the search is continued until the two sections span the entire array : : (adens _search *while do :( +rdiv if [mx then : + else : end end the terminating condition is > is it guaranteed to be reachedin order to establish this guaranteewe must show that under all circumstances the difference - is diminished in each step holds at the beginning of each step the arithmetic mean then satisfies < hencethe difference is indeed diminished by either assigning + to (increasing lor to (decreasing )and the repetition terminates with howeverthe invariant and do not yet establish match certainlyif nno match exists otherwise we must take into consideration that the element [rhad never been compared hencean additional test for equality [rx is necessary in contrast to the first solutionthis algorithm -like linear search -finds the matching element with the least index table search search through an array is sometimes also called table searchparticularly if the keys are themselves structured objectssuch as arrays of numbers or characters the latter is frequently encountered casethe character arrays are called strings or words let us define type string as string array of char and let order on strings and be defined as follows( (aj < xj yj( yei < ((aj < xj yj(xi yi)in order to establish matchwe evidently must find all characters of the comparands to be equal such comparison of structured operands therefore turns out to be search for an unequal pair of comparandsi search for inequality if no unequal pair existsequality is established assuming that the length of the words be quite smallsay less than we shall use linear search in the following solution in most practical applicationsone wishes to consider strings as having variable length this is accomplished by associating length indication with each individual string value using the type declared abovethis length must not exceed the maximum length this scheme allows for sufficient flexibility for many casesyet avoids the complexities of dynamic storage allocation two representations of string