How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Cerebras.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Cerebras during technical interviews.

Implement Binary Search in C++ | Cerebras Coding Question

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.

Input: ([5], 5)

Expected Output: 0

Explanation: Single-element array where the only element matches.

Input: ([5], -5)

Expected Output: -1

Explanation: Single-element array with no match.

Input: ([], 1)

Expected Output: -1

Explanation: Empty array: nothing to find, return -1.

Input: ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 1)

Expected Output: 0

Explanation: Target is the first element (left boundary).

Input: ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 10)

Expected Output: 9

Explanation: Target is the last element (right boundary).

Input: ([-10, -5, -3, -1, 0, 2, 4], -3)

Expected Output: 2

Explanation: Works with negative values; -3 is at index 2.

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.

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.