Binary Search Flashcards
1
Q
What are two ways to find the middle element (midpoint) in binary search?
A
(high - low) / 2 OR low + (high - low) / 2
2
Q
What is the best-case time complexity for binary search?
A
O(1)
3
Q
What is the worst-case time complexity for binary search?
A
O(log n)
4
Q
What is the recursive version of space complexity for binary search? Why?
A
O(log n) due to the function call stack
5
Q
What is the iterative version of space complexity for binary search? Why?
A
O(1) due to no extra memory being used
6
Q
What are 2 advantages binary search has over linear search?
A
1) faster for large, sorted lists
2) reduces the number of comparisons
