implementation in code fragments through we present complete implementation of classsortedtablemapthat supports the sorted map adt the most notable feature of our design is the inclusion of find index utility function this method using the binary search algorithmbut by convention returns the index of the leftmost item in the search interval having key greater than or equal to thereforeif the key is presentit will return the index of the item having that key (recall that keys are unique in map when the key is missingthe function returns the index of the item in the search interval that is just beyond where the key would have been located as technicalitythe method returns index high to indicate that no items of the interval had key greater than we rely on this utility method when implementing the traditional map operations and the new sorted map operations the body of each of the getitem setitem and delitem methods begins with call to find index to determine candidate index at which matching key might be found for getitem we simply check whether that is valid index containing the target to determine the result for setitem recall that the goal is to replace the value of an existing itemif one with key is foundbut otherwise to insert new item into the map the index returned by find index will be the index of the matchif one existsor otherwise the exact index at which the new item should be inserted for delitem we again rely on the convenience of find index to determine the location of the item to be poppedif any our find index utility is equally valuable when implementing the various inexact search methods given in code fragment for each of the methods find ltfind lefind gtand find gewe begin with call to find index utilitywhich locates the first index at which there is an element with key >kif any this is precisely what we want for find geif validand just beyond the index we want for find lt for find gt and find le we need some extra case analysis to distinguish whether the indicated index has key equal to for exampleif the indicated item has matching keyour find gt implementation increments the index before continuing with the process (we omit the implementation of find lefor brevity in all caseswe must properly handle boundary casesreporting none when unable to find key with the desired property our strategy for implementing find range is to use the find index utility to locate the first item with key >start (assuming start is not nonewith that knowledgewe use while loop to sequentially report items until reaching one that has key greater than or equal to the stopping value (or until reaching the end of the tableit is worth noting that the while loop may trivially iterate zero items if the first key that is greater than or equal to start also happens to be greater than or equal to stop this represents an empty range in the map