Q1.What is the prerequisite for standard binary search to work correctly on an array?
Q2.What is the time complexity of binary search on a sorted array of n elements?
Q3.In the classic binary search loop, how is `mid` typically computed to avoid integer overflow?
Q4.What is the space complexity of an iterative binary search implementation?
Q5.What is the space complexity of a typical recursive binary search implementation, accounting for the call stack?
Q6.If arr[mid] < target in a standard ascending binary search, what should happen next?
Q7.What does binary search return, in a typical implementation, if the target is not found?
Q8.Which of these can binary search NOT be directly applied to?
Q9.What is "binary search on the answer" a technique for?
Q10.To find the first (leftmost) occurrence of a target in a sorted array with duplicates, what's a common modification to standard binary search?
Q11.What is the key property that makes binary search still applicable to a rotated sorted array like [4,5,6,7,0,1,2]?
Q12.What does lower_bound(target) typically return in binary search terminology?
Q13.What does upper_bound(target) typically return?
Q14.Why is binary search inefficient on a linked list even if it's sorted?
Q15.What's a common bug when a binary search loop uses `while (low < high)` when the algorithm's invariants require checking `low == high` too?
Q16.What is the maximum number of comparisons binary search needs, approximately, for an array of 1,000,000 elements?
Q17.How would you use binary search to find the square root of a non-negative number x to a given precision, without a built-in sqrt function?
Q18.What does it mean for a binary search "search space" to be monotonic, as required for binary-search-on-answer problems?
Q19.When searching a 2D matrix sorted both row-wise and globally (each row's values greater than the previous row's), what's a binary-search-friendly approach?
Q20.What does "peak element" search using binary search exploit, when finding an element greater than both its neighbors?
Q21.What's the time complexity of binary search combined with an O(n) preprocessing step, used to answer each of q queries?
Q22.Why might an interviewer ask you to implement binary search iteratively instead of recursively?
Q23.What happens to binary search's correctness if the array is sorted descending but the comparison logic assumes ascending order?
Q24.What is the relationship between binary search and the "divide and conquer" algorithmic paradigm?
Q25.If you need the closest value to a target when the exact target isn't present, what should you track during binary search?
