Why Binary Search has O(log n) Time Complexity?

O said as Big O is used to express worst case time complexity. So log(n) is the worst case Time Complexity for the binary search algorithm. Before understanding why Binary Search has a log(n) Time Complexity, let us first see what is even a logarithm.

A logarithm is the power that a number needs to be raised to, to get some other number.
Sounds confusing? Let us understand with an example:-

Let us take the number 8 into consideration. So we need to raise some number to some number to get 8 which we can visualize as:

xˣ = 8

In Computer Science, unless specified otherwise, we can always assume that the number that we want to raise to some power is 2. This number is called the base.

So, now my equation becomes 2ˣ = 8. This same equation can be written as log₂(8) = x. Any guesses on the value of x?

Yes, you got that right!!! The answer is 3. So log₂(8) = 3. That means for n = 8 as the input for the logarithmic function with base 2, the answer comes out to be 3. So we can deduce that if there are 8 elements in the array, the binary search would take a maximum of 3 steps to find the number that you want to find which justifies the worst case scenario as well i.e. Time Complexity for a Binary Search Algorithm = O(log n).

Dry run:
Array: [10, 15, 30, 45, 60, 70, 100, 110]
Target element: 10

Step 1: Start = 0, End = 7
Mid = (Start + End) / 2 = (0 + 7) / 2 = 3
Array[3] = 45

Since 10 < 45, search the left half.

Step 2: Start = 0, End = 2
Mid = (0 + 2) / 2 = 1
Array[1] = 15

Since 10 < 15, search the left half.

Step 3: Start = 0, End = 0
Mid = (0 + 0) / 2 = 0
Array[0] = 10

Target element found at index 0 (position 1). As you noticed the algorithm took 3 steps to find our number which justifies our understanding of logarithmic complexity.

I hope this blog helped you develop a better intuition for how algorithms work. If you have any questions, suggestions, or different approaches to solving a problem, feel free to share them in the comments. I'd love to hear your thoughts and learn from your experiences!