โ† Nagarro questions

Binary Search Mechanics and Termination

Filed under Nagarro

Free read 1 of 3

Maintain 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

  1. Maintain left and right boundaries. Calculate mid = left + (right - left) // 2. Compare arr[mid] to target and halve the search space.

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.