Derive the Time Complexity and Space Complexity of Binary Search Algorithm

Time Complexity:

• Binary Search divides the array in half with each iteration.
• In the worst case, the number of comparisons reduces the search space by half each time.
• This means it will take at most log₂(n) comparisons, where n is the size of the array.

Thus, the time complexity is:

O(log n)

Space Complexity:

• Binary Search requires only a few extra variables (low, high, mid) and does not need additional space proportional to the input size.
• If it’s implemented iteratively, the space complexity is constant.

Thus, the space complexity is:

O(1)