Frontend School

Find Smallest Element Greater Than or Equal to Target

DSA
easy

Find Smallest Element Greater Than or Equal to Target

Easy
Binary Search
Arrays

Overview

Efficiently searching through large, sorted datasets is a fundamental problem in computer science, impacting performance across various applications from database queries to file system lookups. This problem focuses on a common variant of searching in sorted arrays, requiring you to pinpoint a specific type of element efficiently.

What you need to do / Task

Implement a function findFirstGreaterOrEqual that takes a sorted array of integers nums and a target integer. Your task is to find the index of the smallest element in nums that is greater than or equal to target. If no such element exists in the array (i.e., all elements are smaller than target), the function should return -1.

Input & output

  • nums: An array of integers, sorted in non-decreasing order.
  • target: An integer value to search for.
  • Returns: An integer representing the 0-based index of the smallest element in nums that is greater than or equal to target. Returns -1 if no such element is found.

Clarifications

  • Empty Array: If nums is empty, what should be returned?
  • Target Out of Bounds: What if target is smaller than all elements in nums? What if it's larger than all elements?
  • Duplicates: If target (or an element greater than it) appears multiple times, which index should be returned?

Examples

1

Example 1

Input:

nums = [1, 3, 5, 7, 9], target = 6

Output:

3

Note:

The smallest element greater than or equal to 6 is 7, which is at index 3.

2

Example 2

Input:

nums = [1, 3, 5, 7, 9], target = 1

Output:

0

Note:

The smallest element greater than or equal to 1 is 1 itself, at index 0.

3

Example 3

Input:

nums = [1, 3, 5, 7, 9], target = 10

Output:

-1

Note:

All elements in the array are smaller than 10. No such element exists.

4

Example 4

Input:

nums = [2, 2, 2, 2], target = 2

Output:

0

Note:

The smallest element greater than or equal to 2 is the first '2', at index 0.

5

Example 5

Input:

nums = [], target = 5

Output:

-1

Note:

The array is empty, so no element can satisfy the condition.

Constraints

Constraints & assumptions

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • The array nums is guaranteed to be sorted in non-decreasing order.

What interviewers evaluate

  • Algorithmic Efficiency: Correctly applies an optimal search algorithm for sorted data.
  • Edge Case Handling: Addresses scenarios like empty arrays, targets outside the array's range, and duplicate values.
  • Correctness: The solution accurately identifies the required index under all valid conditions.
  • Code Quality: Produces clean, readable, and maintainable code.

Loading editor...