Why complexity of Binary Search is O(log n)?

When you do one operation in binary search we reduce the size of the problem by half. To answer the questions we have to answer, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

1 = N / 2^x

multiply by 2^x:

2^x = N

now do the log₂:

log₂(2^x)    = log₂ N
x log₂(2) = log₂ N
x 1         = log₂ N

this means you can divide log N times until you have everything divided. Which means you have to divide log N (“do the binary search step”) until you found your element.

The same concept explained graphically: