relative orderso we consider only comparisons between and an element in at the root of the decision treeour knowledge rules out no positions in lso all are potential candidates as we take branches in the decision tree based on the result of comparing to an element in lwe gradually rule out potential candidates eventually we reach leaf node in the tree representing the single position in that can contain there must be at least nodes in the tree because we have distinct positions that can be in (any position in lplus not in at allsome path in the tree must be at least log levels deepand the deepest node in the tree represents the worst case for that algorithm thusany algorithm on sorted array requires at least ohm(log ncomparisons in the worst case we can modify this proof to find the average cost lower bound againwe model algorithms using decision trees except now we are interested not in the depth of the deepest node (the worst caseand therefore the tree with the leastdeepest node insteadwe are interested in knowing what the minimum possible is for the "average depthof the leaf nodes define the total path length as the sum of the levels for each node the cost of an outcome is the level of the corresponding node plus the average cost of the algorithm is the average cost of the outcomes (total path length/nwhat is the tree with the least average depththis is equivalent to the tree that corresponds to binary search thusbinary search is optimal in the average case while binary search is indeed an optimal algorithm for sorted list in the worst and average cases when searching sorted arraythere are number of circumstances that might lead us to selecting another algorithm instead one possibility is that we know something about the distribution of the data in the array we saw in section that if each position in is equally likely to hold (equivalentlythe data are well distributed along the full key range)then an interpolation search is (log log nin the average case if the data are not sortedthen using binary search requires us to pay the cost of sorting the list in advancewhich is only worthwhile if many searches will be performed on the list binary search also requires that the list (even if sortedbe implemented using an array or some other structure that supports random access to all elements with equal cost finallyif we know all search requests in advancewe might prefer to sort the list by frequency and do linear search in extreme search distributionsas discussed in section finding the maximum value how can we find the ith largest value in sorted listobviously we just go to the ith position but what if we have an unsorted listcan we do better than to sort itif we are looking for the minimum or maximum valuecertainly we can do