How do you perform binary search on a sorted array to find a target index?
Candidates are asked to write a function that searches for a specific integer in a sorted array using an efficient divide-and-conquer strategy.
Why Interviewers Ask This
This is a classic test of basic algorithmic knowledge and implementation precision. Interviewers want to see if the candidate understands the prerequisites for binary search, such as the requirement for a sorted array. It also evaluates their ability to handle boundary conditions correctly, avoid infinite loops, and achieve the optimal logarithmic time complexity.
How to Answer This Question
Begin by stating the precondition that the input array must be sorted. Describe the logic of maintaining left and right pointers and calculating the middle index. Explain the comparison logic: if the middle element equals the target, return the index; if it is less, move the left pointer; otherwise, move the right pointer. Emphasize handling off-by-one errors and ensuring the loop terminates correctly.
Key Points to Cover
- Requires sorted input array
- Maintain low and high pointers
- Compare mid element with target
- Return index or -1
Sample Answer
I would implement binary search by initializing two pointers, low and high, representing the search boundaries. In each iteration, I calculate the mid index and compare the value at that index with the target. If the target matches, I return the index immediately. If the target is smaller, I adjust the high pointer to mid minus one; if larger, I adjust the low pointer to mid plus one. This continues until the target is found or the pointers cross, returning -1 if not found, achieving O(log n) efficiency.
Common Mistakes to Avoid
- Integer overflow when calculating mid index
- Infinite loops due to incorrect pointer updates
- Ignoring the sorted requirement
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 SachsHow do you perform binary search on a sorted array efficiently?
Easy
Goldman Sachs