( low ( high low ( high high mid low ( mid low ( mid high mid low high ( low high mid figure the steps performed by the binary search algorithm in searching for (ainitial range of items(blocating the midpoint(celiminating the upper half(dmidpoint of the lower half(eeliminating the lower fourthand (ffinding the target item while loop is executed the worst case occurs when the target value is not in the sequencethe same as for the linear search the difference with the binary search is that not every item in the sequence has to be examined before determining the target is not in the sequenceeven in the worst case since the sequence is sortedeach iteration of the loop can eliminate from consideration half of the remaining values as we saw earlier in section when the input size is repeatedly reduced by half during each iteration of loopthere will be log iterations in the worst case thusthe binary search algorithm has worst case time-complexity of (log )which is more efficient than the linear search sorting sorting is the process of arranging or ordering collection of items such that each item and its successor satisfy prescribed relationship the items can be simple valuessuch as integers and realsor more complex typessuch as student records or dictionary entries in either casethe ordering of the items is based on the value of sort key the key is the value itself when sorting simple types or it can be specific component or combination of components when sorting complex types we encounter many examples of sorting in everyday life consider the listings of phone bookthe definitions in dictionaryor the terms in an indexall of which are organized in alphabetical order to make finding an entry much easier as we