Ceiling in a sorted array Easy 0 attempts
GeeksforGeeks ↗

Ceiling in a sorted array

Easy Sorting&Searching GeeksforGeeks

You're given a sorted array arr and a value x. Find the ceiling of x in the array — the smallest element that is greater than or equal to x. Return -1 when no such element exists.

Input Format
Implement ceiling(arr, x). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
arr = [1,2,8,10,10,12,19]
x = 5
Output
8

Example 2

Input
arr = [1,2,8,10]
x = 0
Output
1
Constraints
  • 1 <= arr.length <= 10^5
  • 1 <= arr[i], x <= 10^6
Test Cases (2)
Case 1
Args: [[1,2,8,10,10,12,19],5] Expected: 8
Case 2
Args: [[1,2,8,10],0] Expected: 1
Topics
Sorting&Searching

Binary Search

javascript
function ceiling(arr, x) {
  let lo = 0, hi = arr.length - 1, result = -1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] >= x) { result = arr[mid]; hi = mid - 1; }
    else lo = mid + 1;
  }
  return result;
}

Time: O(log n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript