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.

Gothart

possible duplicate of Where from log(n) comes to O(N) notation – Klement

visual answer to your question: https://mcmap.net/q/40462/-what-does-o-log-n-mean-exactly – Springwood

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).

Frager

Thanks. Clean explanation. Now I am satisified :-) – Gothart

I have been looking for this explanation all day. Thanks. – Manymanya

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

Middendorf

Answer 3

These are all good answers, however I wish to clarify something that I did not consider before. We are asking how many operations does it take to get an array of size 1 from size n. The reason for this is that when the array size is 1, the only element in the array is the element which is to be found and the search operation can be terminated. In other words, when the array size becomes 1, the element that was searched is found.

The way binary search works is by halving the search space of the array and gradually focusing on the matching element. Let's say the size of array is n. Then, in m operations of halving the search space, the size of the array search space becomes n/2^m. When it becomes 1, we have found our element. So equate it to 1 and solve for m.

To summarize, m = log2(n) is the number of operations it would take for the binary search algorithm to reduce the search space from n to 1 and hence, find the element that is searched.

Blackcap