Question

What is the time complexity of binary search and it's derivation?

Answer 1

With a binary search, you eliminate 1/2 the possible entries each iteration, such that at most it would only take 7 compares to find your value (log base 2 of 128 is 7 or 2 to the 7 power is 128.) This is the power of binary search. The time complexity of the binary search algorithm belongs to the O(log n) class.