Skip to question

Q159FreeSystemVerilog

Find lower and upper bounds

Difficulty
Medium
Topic
Arrays
Language
SV
Interview prompt

Question

For a sorted integer array, return the first index with value >= target and the first index with value > target.

Candidate starting point

Implementation scaffold

function automatic int lower_bound_int(
  const ref int values[],
  input int target
);
    // TODO: implement this body.
  endfunction

function automatic int upper_bound_int(
  const ref int values[],
  input int target
);
    // TODO: implement this body.
  endfunction
Reviewed example

Trace one case

Input
values = [1, 2, 2, 2, 5], target = 2
Expected output
lower_bound = 1, upper_bound = 4

The half-open matching range [1,4) contains all three occurrences of 2.

What to cover

Requirements

  1. Return values.size() when the requested bound does not exist.
  2. Handle duplicate targets correctly.
  3. Use half-open search intervals.
Continue practicing
Q182 · Data StructuresUse lower-bound insertion for top-K largestMediumQ037 · Firmware AlgorithmsFind a calibration insertion positionEasy