Câu hỏi phỏng vấn Searching
Câu hỏi

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

Câu trả lời

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

middle

Gợi ý câu hỏi phỏng vấn

senior

Explain what is Ternary Search?

expert

When Jump Search is a better alternative than a Binary Search?

senior

What is the optimal block size for a Jump Search? Explain.

Bình luận

Chưa có bình luận nào

Chưa có bình luận nào