What is the Time Complexity of Binary Search and it's derivation

Question

Accepted Answer

Binary Search has a time complexity of O(log n) and is derived from dividing the search space in half at each step.

Binary Search is a search algorithm that works on sorted arrays.
It starts by comparing the target value to the middle element of the array.
If the target value is smaller, the search continues on the lower half of the array.
If the target value is larger, the search continues on the upper half of the array.
This process is repeated until the target value is found or the search space is empty.
The time complexity of Binary Search is O(log n) because at each step, the search space is divided in half.
This means that the number of steps required to find the target value is proportional to the logarithm of the size of the array.
For example, if the array has 8 elements, Binary Search will take at most 3 steps to find the target value.

Top Medlife Software Engineer interview questions & answers