Binary Search Mechanics and Termination
Filed under Nagarro
Free read 1 of 3Maintain left and right boundaries. Calculate mid = left + (right - left) // 2. Compare arr[mid] to target and halve the search space.
The question
Explain how Binary Search works on a sorted array, state its logarithmic time complexity, and describe the precise termination condition when the target element is absent.
Constraints
- Array must be sorted in ascending order.
- Space complexity should be O(1) iterative.
Examples
- Input
- arr = [1, 3, 5, 7, 9], target = 4
- Output
- Element not found (returns -1)
- Why
- Search space collapses from range [0, 4] to [0, 1] to empty range [1, 0] when left (1) exceeds right (0).
Approach
Maintain left and right boundaries. Calculate mid = left + (right - left) // 2. Compare arr[mid] to target and halve the search space.
If target == arr[mid], return mid. If target < arr[mid], narrow search to left half with right = mid - 1. Otherwise set left = mid + 1.
The loop terminates when left > right. This boundary crossover occurs when target is absent, confirming no remaining elements to check.
Time complexity is O(log N) because each comparison divides the active search space by half. Space complexity is O(1) for iterative implementation.
Tips
- What they are testing: Assesses clear understanding of binary search boundary conditions and why logarithmic reduction occurs.
- Common mistake: Using left < right instead of left <= right in the while loop, which misses checking the final remaining element.
Related Nagarro questions
Collected from public candidate posts and coding forums. Updated Nov 2026.