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_{2 }N , log_{2} N -1, log_{2} N-2, log_{2} N-3, .........., 3, 2, 1, 0
Since the sequence decrements through 1 each time the overall elements in the above series are log_{2 }N + 1. Thus, the number of iterations is log_{2} N + 1 that is of the order of O(log_{2}N).