Ceiling in a sorted array Easy 0 attempts
GeeksforGeeks ↗

Ceiling in a sorted array

Easy Sorting&Searching GeeksforGeeks

Given a sorted array and a value x, find the ceiling of x — the smallest element >= x.

Example: arr = [1, 2, 8, 10, 10, 12, 19], x = 5 → Output: 8

Sample Input
—
Sample Output
—
Constraints
  • 1 <= arr.length <= 10^5
  • 1 <= arr[i], x <= 10^6
Test Cases
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

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