What is the worst case time complexity of binary search?

Binary search is an efficient algorithm for finding an item from a sorted list of items. The key to its effectiveness lies in how it repeatedly divides the search interval in half.

In the worst-case scenario, a binary search will continue to halve the search space until it either locates the target value or concludes that the value is not present. Each division reduces the remaining elements to search by half, which leads to this logarithmic time complexity.

Mathematically, if you have a list of n elements, after the first comparison you have n/2, after the second it becomes n/4, and so forth. This reduction continues until the list is reduced to a single element, which corresponds to the logarithm base 2 of n. Therefore, the worst-case time complexity of binary search is expressed as O(log n).

This efficiency makes binary search significantly faster than linear search (O(n)) for large datasets, as it limits the number of comparisons required to find an element, thus allowing for rapid search operations.