Why to consider binary search running time complexity as log2N

Question

Can someone explain me when it comes to binary search we say the running time complexity is O(log n)? I searched it in Google and got the below,

"The number of times that you can halve the search space is the same as log₂ n".

I know we do halve until we find the search key in the data structure, but why we have to consider it as log₂ n? I understand that e^x is exponential growth and so the log₂ n is the binary decay. But I am unable to interpret the binary search in terms of my logarithm definition understanding.

Answer 1

Think of it like this:

If you can afford to half something m times, (i.e., you can afford to spend time proportional to m), then how large array can you afford to search?

Obviously arrays of size 2^m, right?

So if you can search an array of size n = 2^m, then the time it takes is proportional to m, and solving m for n look like this:

n = 2^m

log₂(n) = log₂(2^m)

log₂(n) = m


Put another way: Performing a binary search on an array of size n = 2^m takes time proportional to m, or equivalently, proportional to log₂(n).

Answer 2

Binary search :-

lets take an example to solve the problem .

suppose we are having 'n' apples and every day half of the apples gets rotten . then after how many days the apple count will be '1'.

first day n apples : a a a a .... (total n)

second day : a a a a..a(total n/2)

third day : a a a .. a(total n/(2^2));

so onn.............. lets suppose after k days the apples left will be 1
i.e n/(2^k) should become 1 atlast

n/(2^k)=1; 2^k=n; applying log to base 2 on both sides

k=log n;

in the same manner in binary search

firstly we are left with n elements then n/2 then n/4 then n/8 so on finally we are left with one ele so time complexity is log n