searching the task of searching is one of most frequent operations in computer programming it also provides an ideal ground for application of the data structures so far encountered there exist several basic variations of the theme of searchingand many different algorithms have been developed on this subject the basic assumption in the following presentations is that the collection of dataamong which given element is to be searchedis fixed we shall assume that this set of elements is represented as an arraysay as aarray of item typicallythe type item has record structure with field that acts as key the task then consists of finding an element of whose key field is equal to given search argument the resulting index isatisfying [ikey xthen permits access to the other fields of the located element since we are here interested in the task of searching onlyand do not care about the data for which the element was searched in the first placewe shall assume that the type item consists of the key onlyi is the key linear search when no further information is given about the searched datathe obvious approach is to proceed sequentially through the array in order to increase step by step the size of the sectionwhere the desired element is known not to exist this approach is called linear search there are two conditions which terminate the search the element is foundi ai the entire array has been scannedand no match was found this results in the following algorithmi : while ( ( [ixdo inc(iend (adens _search *note that the order of the terms in the boolean expression is relevant the invarianti the condition satisfied before and after each loop stepis ( < (ak < ak xexpressing that for all values of less than no match exists note that the values of before and after each loop step are different the invariant is preserved nevertheless due to the while-clause from this and the fact that the search terminates only if the condition in the while-clause is falsethe resulting condition is derived as(( nor (ai )(ak < ak xthis condition not only is our desired resultbut also implies that when the algorithm did find matchit found the one with the least indexi the first one implies that no match exists termination of the repetition is evidently guaranteedbecause in each step is increased and therefore certainly will reach the limit after finite number of stepsin factafter stepsif no match exists each step evidently requires the incrementing of the index and the evaluation of boolean expression could this task be simplifedand could the search thereby be acceleratedthe only possibility lies in finding simplification of the boolean expression which notably consists of two factors hencethe only chance for finding simpler solution lies in establishing condition consisting of single factor that implies both factors this is possible only by guaranteeing that match will be foundand is achieved by posting an additional element with value at the end of the array we call this auxiliary element sentinelbecause it prevents the search from passing beyond the index limit the array is now declared as