in a sorted list binary search is carried out by

Question

In a sorted list, Binary search is carried out by dividing the list into two parts depends on the comparison of the key. Since the search interval halves each time, the iteration occur in the search. The search interval will look like as after each iteration

N, N/2,  N/4, N/8 , .......... 8, 4, 2, 1

The number of iterations (number of elements in the series) is not so evident through the above series. However, if we take logs of each element of the series, then

log₂ N , log₂ N -1,  log₂ N-2, log₂ N-3, .........., 3, 2, 1, 0

Since the sequence decrements through 1 each time the overall elements in the above series are log₂ N + 1. Thus, the number of iterations is log₂ N + 1 that is of the order of O(log₂N).