What is the maximum number of guesses needed in the binary search in the range 1 to n?
A binary search is an efficient search mechanism for a list of N data values which are sorted according to a well defined criterion (for example, in alphabetical or numerical order). Essentially this means that the comparison of the known target value with an arbitrary member of the list will yield one of three results: the two are the same, ie the search is complete, or the target value lies above or below the current position. The strategy is simple. The centre value of the N data points is selected and a comparison with the target value made. If unsuccessful, the position of the required element in the list is known to be either above or below the current position. This enables half of the data values to be rejected, and the procedure repeated on the remaining half (hence ‘binary search’). In the worst case the search will be successful when the number of remaining data values has been reduced to one; this occurs the first time the number n of steps or guesses meets the condition 2^
