Consider the task of searching a sorted array a1n for a give

Consider the task of searching a sorted array a[1..n] for a given element w. Show that any algorithm that accesses the array only via comparisons (that is, by asking questions of the form “is a[i] z?”), must take (log n) steps.

Solution

Let k be the number of recursive calls in binary search algorithm.
In every recursion you half an input segment.   
2*2*2*.....k times= 2^k. This 2^k<=n where n=input size(number of elements)
take log base 2 both side.
Hence k=O(log(n))