Implement Binary Search in C++

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.

Implement Binary Search

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)

Hints

1. Maintain two pointers, lo and hi, bounding the search window. Initialize lo = 0 and hi = len(nums) - 1.
2. 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).
3. 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.