Why time complexity of binary search is Logn?

View Discussion

Improve Article

Save Article

Like Article

View Discussion

Improve Article

Save Article

Like Article

This is used to search a sorted array by repeatedly dividing the search interval in half. 

Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the left half. Otherwise, narrow it to the right half. Repeatedly check until the value is found or the interval is empty. 

Examples: 

Input: arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, target = 23

Below is the step-by-step procedure to find the given target element using binary search:

Iteration 1: 

Array: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91

• Select the middle element. (here 16)
• Since 23 is greater than 16, so we divide the array into two halves and consider the sub-array after element 16.
• Now this subarray with the elements after 16 will be taken into the next iteration.

Iteration 2: 

Array: 23, 38, 56, 72, 91

• Select the middle element. (now 56)
• Since 23 is smaller than 56, so we divide the array into two halves and consider the sub-array before element 56.
• Now this subarray with the elements before 56 will be taken into next iteration.

Iteration 3: 

Array: 23, 38

• Select the middle element. (now 23)
• Since 23 is the middle element. So the iterations will now stop.
• Let’s say the iteration in Binary Search terminates after k iterations. In the above example, it terminates after 3 iterations, so here k = 3
• At each iteration, the array is divided by half. So let’s say the length of the array at any iteration is n

Length of array = n

Length of array = n/2

Length of array = (n/2)/2 = n/22

Length of array = n/2k

Also, we know that after k iterations, the length of the array becomes 1 Therefore, the Length of the array 
n/2k = 1
=> n = 2k
Applying log function on both sides: 

=> log2n = log22k

=> log2n = k * log22

As (loga (a) = 1) Therefore, k = log2(n)

Knowing the complexity of algorithms beforehand is one thing, and other thing is knowing the reason behind it being like that.

Whether you’re a CS graduate or someone who wants to deal with optimization problems effectively, this is something that you must understand if you want to use your knowledge for solving actual problems.

Complexities like O(1) and O(n) are simple and straightforward. O(1) means an operation which is done to reach an element directly (like a dictionary or hash table), O(n) means first we would have to search it by checking n elements, but what could O(log n) possibly mean?

One place where you might have heard about O(log n) time complexity the first time is Binary search algorithm. So there must be some type of behavior that algorithm is showing to be given a complexity of log n. Let us see how it works.

Since binary search has a best case efficiency of O(1) and worst case (average case) efficiency of O(log n), we will look at an example of the worst case. Consider a sorted array of 16 elements.

For the worst case, let us say we want to search for the the number 13.

A sorted array of 16 elements

Selecting the middle element as pivot (length / 2)

Since 13 is less than pivot, we remove the other half of the array

Repeating the process for finding the middle element for every sub-array

You can see that after every comparison with the middle term, our searching range gets divided into half of the current range.

So, for reaching one element from a set of 16 elements, we had to divide the array 4 times,

We can say that,

Simplified Formula

Similarly, for n elements,

Generalization

Separating the power for the numerator and denominator

Multiplying both sides by 2^k

Final result

Now, let us look at the definition of logarithm, it says that

A quantity representing the power to which a fixed number (the base) must be raised to produce a given number.

Which makes our equation into

Logarithmic form

So the log n actually means something doesn’t it? A type of behavior nothing else can represent.

Well, i hope the idea of it is clear in your mind. When working in the field of computer science, it is always helpful to know such stuff (and is quite interesting too). Who knows, maybe you’re the one in your team who is able to find an optimized solution for a problem, just because you know what you’re dealing with. Good luck!