Quick Overview

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.

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.

Overview: 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.

Read the full Cerebras Software Engineer interview experience this question came from

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

  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.

Implement Binary Search

mediumCerebrasSoftware Engineer

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)

Examples

Example 1
Input
([-1, 0, 3, 5, 9, 12], 9)
Output
4
Notes
Target 9 sits at index 4.
Example 2
Input
([-1, 0, 3, 5, 9, 12], 2)
Output
-1
Notes
Target 2 is not present, so return -1.

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)

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Sample call
binary_search([-1, 0, 3, 5, 9, 12], 9)
Language
Case 1
Input
([-1, 0, 3, 5, 9, 12], 9)
Expected
4
Case 2
Input
([-1, 0, 3, 5, 9, 12], 2)
Expected
-1

Browse More Questions