Explain why complexity of Binary Search is O(log n) ?
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...
middle
Gợi ý câu hỏi phỏng vấn
Chưa có bình luận nào