searching and sorting working with sorted lists the efficiency of some algorithms can be improved when working with sequences containing sorted values we saw this earlier when performing search using the binary search algorithm on sorted sequence sorting algorithms can be used to create sorted sequencebut they are typically applied to an unsorted sequence in which all of the values are known and the collection remains static in other wordsno new items will be added to the sequence nor will any be removed in some problemslike the set abstract data typethe collection does not remain static but changes as new items are added and existing ones are removed if sorting algorithm were applied to the underlying list each time new value is added to the setthe result would be highly inefficient since even the best sorting algorithm requires ( log ntime insteadthe sorted list can be maintained as the collection changes by inserting the new item into its proper position without having to re-sort the entire list note that while the sorting algorithms from the previous section all require ( time in the worst casethere are more efficient sorting algorithms (which will be covered in that only require ( log ntime maintaining sorted list to maintain sorted list in real timenew items must be inserted into their proper position the new items cannot simply be appended at the end of the list as they may be out of order insteadwe must locate the proper position within the list and use the insert(method to insert it into the indicated position consider the sorted list from figure if we want to add to that listthen it must be inserted at position following value to find the position of new item within sorted lista modified version of the binary search algorithm can be used the binary search uses divide and conquer strategy to reduce the number of items that must be examined to find target item or to determine the target is not in the list instead of returning true or false indicating the existence of valuewe can modify the algorithm to return the index position of the target if it' actually in the list or where the value should be placed if it were inserted into the list the modified version of the binary search algorithm is shown in listing note the change to the two return statements if the target value is contained in the listit will be found in the same fashion as was done in the original version of the algorithm instead of returning truehoweverthe new version returns its index position when the target is not in the listwe need the algorithm to identify the position where it should be inserted consider the illustration in figure which shows the changes to the three variables lowmidand high as the binary search algorithm progresses in searching for value the while loop terminates when either the low or high range variable crosses the otherresulting in the condition low high upon termination of the loopthe low variable will contain the position where the new value should be placed this index can then be supplied to the insert(method to insert the new