What is time complexity of Binary Search?
Binary search is also commonly known as half-interval search or logarithmic search. It is a type of search algorithm that can be used to find the position of a target value within a sorted array. The way binary search works is that it compares the target value to the middle element of the array. If the values are unequal, then the half in which the target value cannot exist is eliminated and is not searched. Binary Search then continues to search he remaining half in the same way until the target value is found.
Binary search runs in at worst logarithmic time, making O(log n) comparisons. It can also be said that O(log n) is the time complexity of Binary Search.
At a glance the complexity table is like this -
- Worst case performance : O(log2 n)
- Best case performance : O(1)
- Average case performance: O(log2 n)
- Worst case space complexity: O(1)