Explain why complexity of Binary Search is O(log n) ?

The time complexity of binary search is O(log n) because the algorithm repeatedly halves the search space in each iteration[1][2][3][4][5].

Here's why:

• Binary search works on a sorted array. It compares the target element to the middle element of the array[1][5].

• If the target is less than the middle element, the algorithm discards the right half of the array and recursively searches the left half[1][3].

• If the target is greater than the middle element, the algorithm discards the left half of the array and recursively searches the right half[1][3].

• This process of halving the search space continues until the target is found or the search space is reduced to an empty set[1][5].

• In the worst case, the algorithm performs this halving operation log2(n) times before the search space is reduced to a single element[1][3][4].

• For example, if the array has 1024 elements, the maximum numb...