sorted search tables several data structures can efficiently support the sorted map adtand we will examine some advanced techniques in section and in this sectionwe begin by exploring simple implementation of sorted map we store the map' items in an array-based sequence so that they are in increasing order of their keysassuming the keys have naturally defined order (see figure we refer to this implementation of map as sorted search table figure realization of map by means of sorted search table we show only the keys for this mapso as to highlight their ordering as was the case with the unsorted table map of section the sorted search table has space requirement that is ( )assuming we grow and shrink the array to keep its size proportional to the number of items in the map the primary advantage of this representationand our reason for insisting that be array-basedis that it allows us to use the binary search algorithm for variety of efficient operations binary search and inexact searches we originally presented the binary search algorithm in section as means for detecting whether given target is stored within sorted sequence in our original presentation (code fragment on page ) binary search function returned true of false to designate whether the desired target was found while such an approach could be used to implement the contains method of the map adtwe can adapt the binary search algorithm to provide far more useful information when performing forms of inexact search in support of the sorted map adt the important realization is that while performing binary searchwe can determine the index at or near where target might be found during successful searchthe standard implementation determines the precise index at which the target is found during an unsuccessful searchalthough the target is not foundthe algorithm will effectively determine pair of indices designating elements of the collection that are just less than or just greater than the missing target as motivating exampleour original simulation from figure on page shows successful binary search for target of using the same data we portray in figure had we instead been searching for the first four steps of the algorithm would be the same the subsequent difference is that we would make an additional call with inverted parameters high= and low= effectively concluding that the missing target lies in the gap between values and in that example