chap searching this and the following treat these three approaches in turn any of these approaches are potentially suitable for implementing the dictionary adt introduced in section howevereach has different performance characteristics that make it the method of choice in particular circumstances the current considers methods for searching data stored in lists and tables table is simply another term for an array list in this context means any list implementation including linked list or an array most of these methods are appropriate for sequences ( duplicate key values are allowed)although special techniques applicable to sets are discussed in section the techniques from the first three sections of this are most appropriate for searching collection of records stored in ram section discusses hashinga technique for organizing data in table such that the location of each record within the table is function of its key value hashing is appropriate when records are stored either in ram or on disk discusses tree-based methods for organizing information on diskincluding commonly used file structure called the -tree nearly all programs that must organize large collections of records stored on disk use some variant of either hashing or the -tree hashing is practical for only certain access functions (exactmatch queriesand is generally appropriate only when duplicate key values are not allowed -trees are the method of choice for disk-based applications anytime hashing is not appropriate searching unsorted and sorted arrays the simplest form of search has already been presented in example the sequential search algorithm sequential search on an unsorted list requires th(ntime in the worst case how many comparisons does linear search do on averagea major consideration is whether is in list at all we can simplify our analysis by ignoring everything about the input except the position of if it is found in thuswe have distinct possible eventsthat is in one of positions to in (each with its own probability)or that it is not in at all we can express the probability that is not in as ( = where (xis the probability of event ( [ ]