realization of dictionary by means of an ordered search table we show only the keys for this dictionaryso as to highlight their ordering the space requirement of an ordered search table is ( )which is similar to the list-based dictionary implementation (section )assuming we grow and shrink the array supporting the array list to keep the size of this array proportional to the number of entries in unlike an unordered listhoweverperforming updates in search table takes considerable amount of time in particularperforming the insert( ,voperation in search table requires (ntimesince we need to shift up all the entries in the array list with key greater than to make room for the new entry (kva similar observation applies to the operation remove ( )since it takes (ntime to shift all the entries in the array list with key greater than to close the "holeleft by the removed entry (or entriesthe search table implementation is therefore inferior to the log file in terms of the worst-case running times of the dictionary update operations neverthelesswe can perform the find method much faster in search table binary search significant advantage of using an ordered array list to implement dictionary with entries is that accessing an element of by its index takes ( time we recallfrom section that the index of an element in an array list is the number of elements preceding it thusthe first element in has index and the last element has index the elements stored in are the entries of dictionary dand since is orderedthe entry at index has key no smaller than the keys of the entries at indices and no larger than the keys of the entries at indices this observation allows us to quickly "home inon search key using variant of the children' game "high-low we call an entry of candidate ifat the current stage of the searchwe cannot rule out that this entry has key equal to the algorithm maintains two parameterslow and highsuch that all the candidate entries have index at least low and at most high in initiallylow and high we then compare to the key of the median candidate ethat isthe entry with index mid (low high)/ we consider three cases