Frontend School

Find Ceiling Element in Sorted Array

DSA
easy

Find Ceiling Element in Sorted Array

Easy
Binary Search
Arrays

Overview

At Lenskart, efficiently managing our vast product catalog is crucial. Imagine our product SKUs are sorted by a specific metric, like a unique identifier or a composite score. When a customer searches for a product or our internal systems need to locate the first product meeting a certain threshold (e.g., a SKU ID greater than or equal to a specific value), we need a rapid way to find that item. This problem challenges you to implement an efficient search algorithm for such a scenario.

What you need to do / Task

Implement a function findCeiling that takes a sorted array of integers arr and an integer target. Your task is to return the 0-based index of the first element in arr that is greater than or equal to target. If no such element exists in the array, the function should return -1.

Input & output

  • Input:
    • arr: An array of integers, sorted in non-decreasing order.
    • target: An integer value.
  • Output:
    • An integer representing the 0-based index of the first element in arr that is greater than or equal to target. If no such element exists, return -1.

Clarifications

  • Empty array: If arr is empty, return -1, as no elements exist.
  • Target larger than all elements: If target is greater than all elements in arr, return -1, as no element satisfies the condition.
  • Target smaller than all elements: If target is smaller than or equal to the first element in arr, you should return the index of the first element (index 0).
  • Duplicates: The array arr can contain duplicate values. If multiple elements are equal to target, you should still return the index of the first occurrence that satisfies the 'greater than or equal' condition.

Examples

1

Example 1

Input:

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

Output:

3

Note:

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

2

Example 2

Input:

arr = [10, 20, 30, 40], target = 5

Output:

0

Note:

The first element greater than or equal to 5 is 10, which is at index 0.

3

Example 3

Input:

arr = [10, 20, 30, 40], target = 45

Output:

-1

Note:

There is no element in the array greater than or equal to 45.

4

Example 4

Input:

arr = [2, 4, 4, 6, 8], target = 4

Output:

1

Note:

The first element greater than or equal to 4 is 4, which is at index 1. Even though arr[2] is also 4, we need the first occurrence.

Constraints

Constraints & assumptions

  • 0 <= arr.length <= 10^5
  • -10^9 <= arr[i], target <= 10^9
  • arr is sorted in non-decreasing order.

Out of scope

  • You do not need to validate if the input arr is indeed sorted. Assume it always is.
  • Error handling for non-integer inputs or non-array inputs.

What interviewers evaluate

  • Correctness: The solution must correctly identify the ceiling element's index for all valid inputs, including edge cases.
  • Efficiency: The solution should achieve optimal time complexity for searching in a sorted array (O(log N)).
  • Clarity & Readability: The code should be well-structured, easy to understand, and follow standard coding practices.
  • Edge Case Handling: Demonstrates robust handling of scenarios like empty arrays, target outside the array's range, and arrays with a single element.

Loading editor...