Implement Binary Search in C++
Company: Cerebras
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
From scratch in C++, implement binary search over a sorted array to locate a target value. Provide a correct iterative implementation, handle not-found cases, and state the algorithm’s time and space complexity.
Quick Answer: This question evaluates proficiency in implementing binary search in C++, focusing on iterative control flow, correct handling of not-found cases, boundary conditions, and understanding of algorithmic correctness.
From scratch, implement binary search over a sorted (ascending) integer array to locate a target value. Return the index of the target if it is present, otherwise return -1. Use an iterative implementation that runs in O(log n) time. Handle the not-found case and edge cases such as an empty array or a single-element array.
Example 1:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4 (nums[4] == 9)
Example 2:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1 (2 is not in nums)
Constraints
- 0 <= nums.length <= 10^5
- nums is sorted in strictly ascending order
- -10^9 <= nums[i], target <= 10^9
- An iterative solution is required (O(1) auxiliary space)
Examples
Input: ([-1, 0, 3, 5, 9, 12], 9)
Expected Output: 4
Explanation: Target 9 sits at index 4.
Input: ([-1, 0, 3, 5, 9, 12], 2)
Expected Output: -1
Explanation: Target 2 is not present, so return -1.
Hints
- Maintain two pointers, lo and hi, bounding the search window. Initialize lo = 0 and hi = len(nums) - 1.
- On each step compute mid = (lo + hi) // 2 and compare nums[mid] with target: equal means you found it; smaller means search the right half (lo = mid + 1); larger means search the left half (hi = mid - 1).
- Loop while lo <= hi. If the loop exits without a match, the target is absent, so return -1. An empty array makes hi = -1, so the loop never runs and you correctly return -1.