How do you perform binary search on a sorted array efficiently?
The candidate is asked to implement a search function that finds a target value in a sorted array with logarithmic time complexity. This is a classic test of divide-and-conquer logic.
Why Interviewers Ask This
Binary search is a foundational algorithm used extensively in production code for searching and sorting operations. Interviewers ask this to verify that the candidate understands the prerequisites for binary search, such as the necessity of a sorted array. They are also testing the candidate's ability to write clean, bug-free iterative or recursive code without off-by-one errors, which are common in this specific algorithm.
How to Answer This Question
Begin by stating the precondition that the input array must be sorted. Define the left and right boundaries and calculate the middle index carefully to avoid integer overflow. Explain the comparison logic: if the middle element equals the target, return the index; otherwise, adjust the boundaries based on whether the target is smaller or larger. Conclude by emphasizing the O(log n) time complexity advantage over linear search.
Key Points to Cover
- Verify array is sorted before starting
- Calculate mid index safely to prevent overflow
- Adjust search boundaries based on comparison results
- Achieve O(log n) time complexity
Sample Answer
To search efficiently in a sorted array, I use binary search. I maintain two pointers, left and right, initialized to the start and end of the array. In each iteration, I calculate the mid-point and compare the element at mid with the target. If they match, I return the index immediately. If the target is less than the mid element, I discard the right half by setting right to mid minus one. Conversely, if it is greater, I discard the left half. This process repeats until the element is found or the search space is exhausted, ensuring O(log n) performance.
Common Mistakes to Avoid
- Forgetting to check if the array is sorted
- Creating infinite loops due to incorrect boundary updates
- Integer overflow when calculating (left + right) / 2
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
How do you implement binary search on a sorted array?
Easy
MicrosoftWhat is the difference between value type and reference type?
Easy
TCSHow do you add two numbers represented by linked lists?
Medium
AmazonWrite Selenium and Java code to automate an Amazon search
Medium
InfosysHow do you implement a queue using two stacks?
Medium
Goldman SachsWhat is the optimal path to maximize collected rocks in a grid?
Hard
Goldman Sachs