chap algorithm analysis position key figure an illustration of binary search on sorted array of positions consider search for the position with value binary search first checks the value at position because kthe desired value cannot appear in any position below in the array nextbinary search checks the value at position because kthe desired value (if it existsmust be between positions and position is checked next againits value is too great the final search is at position which contains the desired value thusfunction binary returns position alternativelyif were then the same series of record accesses would be made after checking position binary would return value of nindicating that the search is unsuccessful to find the cost of this algorithm in the worst casewe can model the running time as recurrence and then find the closed-form solution each recursive call to binary cuts the size of the array approximately in halfso we can model the worst-case cost as followsassuming for simplicity that is power of two (nt( / for ( if we expand the recurrencewe find that we can do so only log times before we reach the base caseand each expansion adds one to the cost thusthe closedform solution for the recurrence is (nlog function binary is designed to find the (singleoccurrence of and return its position special value is returned if does not appear in the array this algorithm can be modified to implement variations such as returning the position of the first occurrence of in the array if multiple occurrences are allowedand returning the position of the greatest value less than when is not in the array comparing sequential search to binary searchwe see that as growsthe th(nrunning time for sequential search in the average and worst cases quickly becomes much greater than the th(log nrunning time for binary search taken in isolationbinary search appears to be much more efficient than sequential search this is despite the fact that the constant factor for binary search is greater than that for sequential searchbecause the calculation for the next search position in binary search is more expensive than just incrementing the current positionas sequential search does note however that the running time for sequential search will be roughly the same regardless of whether or not the array values are stored in order in contrast