How do you implement binary search on a sorted array?
Candidates must demonstrate the ability to write code or explain the logic for finding an element in a sorted array by halving the search space.
Why Interviewers Ask This
Binary search is a fundamental algorithm that tests your grasp of divide-and-conquer strategies and index manipulation. Interviewers use it to check if you understand time complexity constraints (O(log n)) and edge cases like empty arrays or elements not present. It also evaluates your coding style, including loop conditions and boundary handling, which are critical for avoiding infinite loops or off-by-one errors.
How to Answer This Question
Clearly state the pre-condition: the array must be sorted. Describe setting low and high pointers at the start and end of the array. Explain the loop condition where low is less than or equal to high. Detail the calculation of the mid-point and how to adjust low or high based on comparison with the target. Always handle the case where the element is not found by returning -1. Mention the time complexity at the end.
Key Points to Cover
- Requirement of sorted input
- Initialization of low and high pointers
- Loop termination conditions
- Handling of not-found scenario
Sample Answer
To implement binary search, I first ensure the array is sorted. I initialize two pointers, low at index 0 and high at the last index. While low is less than or equal to high, I calculate the middle index. If the element at mid equals the target, I return mid. If the target is smaller, I move the high pointer to mid minus one; otherwise, I move low to mid plus one. If the loop terminates without finding the element, I return -1. This approach ensures O(log n) time complexity.
Common Mistakes to Avoid
- Using integer overflow when calculating mid
- Infinite loops due to incorrect pointer updates
- Forgetting to return -1 for missing elements
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
What is the difference between value type and reference type?
Easy
TCSHow do you perform binary search on a sorted array efficiently?
Easy
Goldman SachsHow do you add two numbers represented by linked lists?
Medium
AmazonWrite Selenium and Java code to automate an Amazon search
Medium
InfosysConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftDiscuss ACID vs. BASE properties
Easy
Microsoft