Ceiling in a sorted array

Last Updated : 23 Jul, 2025

Given a sorted array and a value x, find index of the ceiling of x. The ceiling of x is the smallest element in an array greater than or equal to x.

Note: In case of multiple occurrences of ceiling of x, return the index of the first occurrence.

Examples :

Input: arr[] = [1, 2, 8, 10, 10, 12, 19], x = 5
Output: 2
Explanation: Smallest number greater than 5 is 8, whose index is 2.
Input: arr[] = [1, 2, 8, 10, 10, 12, 19], x = 20
Output: -1
Explanation: No element greater than 20 is found. So output is -1.
Input: arr[] = [1, 1, 2, 8, 10, 10, 12, 19], x = 0
Output: 0
Explanation: Smallest number greater than 0 is 1, whose indices are 0 and 1. The index of the first occurrence is 0.

[Naive Method] - Linear Search - O(n) Time and O(1) Space

If x is smaller than or equal to the first element in the array then return 0(index of the first element).
Else linearly search for an index i such that x lies between arr[i] and arr[i+1].
If we do not find an index i in step 2, then return -1.

C++

#include <bits/stdc++.h> using namespace std; /* Function to get index of ceiling of x in arr */ int ceilSearch(vector<int>& arr, int x)  {   /* If x is smaller than or equal to first element,   then return the first element */  if(x <= arr[0])   return 0;     /* Otherwise, linearly search for ceil value */  for(int i = 0; i < arr.size() - 1; i++)   {   if(arr[i] == x)   return i;     /* if x lies between arr[i] and arr[i+1] including   arr[i+1], then return arr[i+1] */  if(arr[i] < x && arr[i+1] >= x)   return i+1;   }   /* If we reach here then x is greater than the last element   of the array, return -1 in this case */  return -1;  }  /* Driver code*/ int main()  {   vector<int> arr = {1, 2, 8, 10, 10, 12, 19};   int x = 3;   int index = ceilSearch(arr, x);   if(index == -1)   cout << "Ceiling of " << x << " doesn't exist in array ";   else  cout << "ceiling of " << x << " is " << arr[index];   return 0;  }

#include <stdio.h> #include <stdlib.h> /* Function to get index of ceiling of x in arr */ int ceilSearch(int arr[], int n, int x)  {   /* If x is smaller than or equal to first element,   then return the first element */  if(x <= arr[0])   return 0;     /* Otherwise, linearly search for ceil value */  for(int i = 0; i < n - 1; i++)   {   if(arr[i] == x)   return i;     /* if x lies between arr[i] and arr[i+1] including   arr[i+1], then return arr[i+1] */  if(arr[i] < x && arr[i+1] >= x)   return i+1;   }   /* If we reach here then x is greater than the last element   of the array, return -1 in this case */  return -1;  }  /* Driver code*/ int main()  {   int arr[] = {1, 2, 8, 10, 10, 12, 19};   int n = sizeof(arr) / sizeof(arr[0]);  int x = 3;   int index = ceilSearch(arr, n, x);   if(index == -1)   printf("Ceiling of %d doesn't exist in array ", x);   else  printf("ceiling of %d is %d", x, arr[index]);   return 0;  }

Java

import java.util.Arrays; /* Function to get index of ceiling of x in arr */ class GfG {  static int ceilSearch(int[] arr, int x)   {   /* If x is smaller than or equal to first element,   then return the first element */  if(x <= arr[0])   return 0;     /* Otherwise, linearly search for ceil value */  for(int i = 0; i < arr.length - 1; i++)   {   if(arr[i] == x)   return i;     /* if x lies between arr[i] and arr[i+1] including   arr[i+1], then return arr[i+1] */  if(arr[i] < x && arr[i+1] >= x)   return i+1;   }   /* If we reach here then x is greater than the last element   of the array, return -1 in this case */  return -1;   }   /* Driver code*/  public static void main(String[] args)   {   int[] arr = {1, 2, 8, 10, 10, 12, 19};   int x = 3;   int index = ceilSearch(arr, x);   if(index == -1)   System.out.println("Ceiling of " + x + " doesn't exist in array ");   else  System.out.println("ceiling of " + x + " is " + arr[index]);   } }

Python

# Function to get index of ceiling of x in arr def ceil_search(arr, x): # If x is smaller than or equal to first element, # then return the first element if x <= arr[0]: return 0 # Otherwise, linearly search for ceil value for i in range(len(arr) - 1): if arr[i] == x: return i # if x lies between arr[i] and arr[i+1] including # arr[i+1], then return arr[i+1] if arr[i] < x and arr[i + 1] >= x: return i + 1 # If we reach here then x is greater than the last element # of the array, return -1 in this case return -1 # Driver code arr = [1, 2, 8, 10, 10, 12, 19] x = 3 index = ceil_search(arr, x) if index == -1: print(f"Ceiling of {x} doesn't exist in array") else: print(f"Ceiling of {x} is {arr[index]}")

using System; using System.Linq; class Program {  /* Function to get index of ceiling of x in arr */  static int CeilSearch(int[] arr, int x)   {   /* If x is smaller than or equal to first element,   then return the first element */  if(x <= arr[0])   return 0;     /* Otherwise, linearly search for ceil value */  for(int i = 0; i < arr.Length - 1; i++)   {   if(arr[i] == x)   return i;     /* if x lies between arr[i] and arr[i+1] including   arr[i+1], then return arr[i+1] */  if(arr[i] < x && arr[i + 1] >= x)   return i + 1;   }   /* If we reach here then x is greater than the last element   of the array, return -1 in this case */  return -1;   }   /* Driver code*/  static void Main()   {   int[] arr = {1, 2, 8, 10, 10, 12, 19};   int x = 3;   int index = CeilSearch(arr, x);   if(index == -1)   Console.WriteLine($"Ceiling of {x} doesn't exist in array");   else  Console.WriteLine($"ceiling of {x} is {arr[index]}");   } }

JavaScript

// Function to get index of ceiling of x in arr function ceilSearch(arr, x) {  // If x is smaller than or equal to first element,  // then return the first element  if (x <= arr[0]) return 0;  // Otherwise, linearly search for ceil value  for (let i = 0; i < arr.length - 1; i++) {  if (arr[i] === x) return i;    // if x lies between arr[i] and arr[i+1] including  // arr[i+1], then return arr[i+1]  if (arr[i] < x && arr[i + 1] >= x) return i + 1;  }  // If we reach here then x is greater than the last element  // of the array, return -1 in this case  return -1; } // Driver code const arr = [1, 2, 8, 10, 10, 12, 19]; const x = 3; const index = ceilSearch(arr, x); if (index === -1) {  console.log(`Ceiling of ${x} doesn't exist in array`); } else {  console.log(`Ceiling of ${x} is ${arr[index]}`); }

Output

ceiling of 3 is 8

[Expected Approach] - Binary Search - O(Log n) Time and O(1) Space

Since the input array is sorted, we can use binary search.

Find the mid point.
Else If arr[mid] < x, go to the right side
Else (arr[mid] >= x), we found a potential candidate for ceiling. Go to the left side and try finding a smaller value which is greater than or equal to x.

Let us understand the approach with an example

arr = [1, 2, 8, 10, 10, 12, 19] , x = 3
Initial: lo = 0, hi = 6, mid = 3 → arr[3] = 10 (res = 10, Move Left)
Step 2: lo = 0, hi = 2, mid = 1 → arr[1] = 2 (Move Right)
Step 3: lo = 2, hi = 2, mid = 2 → arr[2] = 8 (res = 8, Move Left)
Final: lo > hi, return res = 2

C++

#include <bits/stdc++.h> using namespace std; /* Function to find the ceiling of x using  binary search */ int ceilSearch(vector<int>& arr, int x) {  int lo = 0, hi = arr.size() - 1, res = -1;    while (lo <= hi) {  int mid = lo + (hi - lo) / 2;    if (arr[mid] < x)  lo = mid + 1;     else { // Potential ceiling found  res = mid;   hi = mid - 1;  }  }  return res;  } int main() {  vector<int> arr = {1, 2, 8, 10, 10, 12, 19};  int x = 3;  int index = ceilSearch(arr, x);    if (index == -1)   cout << "Ceiling of " << x << " doesn't exist in array";  else  cout << "Ceiling of " << x << " is " << arr[index];  return 0; }

#include <stdio.h> #include <stdlib.h> /* Function to find the ceiling of x using  binary search */ int ceilSearch(int arr[], int n, int x) {  int lo = 0, hi = n - 1, res = -1;    while (lo <= hi) {  int mid = lo + (hi - lo) / 2;  if (arr[mid] < x)  lo = mid + 1;     else { // Potential ceiling found  res = mid;   hi = mid - 1;  }  }  return res;  } int main() {  int arr[] = {1, 2, 8, 10, 10, 12, 19};  int n = sizeof(arr) / sizeof(arr[0]);  int x = 3;  int index = ceilSearch(arr, n, x);    if (index == -1)   printf("Ceiling of %d doesn't exist in array\n", x);  else  printf("Ceiling of %d is %d\n", x, arr[index]);  return 0; }

Java

import java.util.Arrays; public class Main {    /* Function to find the ceiling of x using  binary search */  static int ceilSearch(int[] arr, int x) {  int lo = 0, hi = arr.length - 1, res = -1;    while (lo <= hi) {  int mid = lo + (hi - lo) / 2;  if (arr[mid] < x)  lo = mid + 1;     else { // Potential ceiling found  res = mid;   hi = mid - 1;  }  }  return res;   }  public static void main(String[] args) {  int[] arr = {1, 2, 8, 10, 10, 12, 19};  int x = 3;  int index = ceilSearch(arr, x);    if (index == -1)   System.out.println("Ceiling of " + x + " doesn't exist in array");  else  System.out.println("Ceiling of " + x + " is " + arr[index]);  } }

Python

# Function to find the ceiling of x using binary search def ceilSearch(arr, x): lo = 0 hi = len(arr) - 1 res = -1 while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] < x: lo = mid + 1 else: # Potential ceiling found res = mid hi = mid - 1 return res if __name__ == "__main__": arr = [1, 2, 8, 10, 10, 12, 19] x = 3 index = ceilSearch(arr, x) if index == -1: print(f"Ceiling of {x} doesn't exist in array") else: print(f"Ceiling of {x} is {arr[index]}")

using System; using System.Linq; class Program {  /* Function to find the ceiling of x using  binary search */  static int CeilSearch(int[] arr, int x) {  int lo = 0, hi = arr.Length - 1, res = -1;    while (lo <= hi) {  int mid = lo + (hi - lo) / 2;  if (arr[mid] < x)  lo = mid + 1;     else { // Potential ceiling found  res = mid;   hi = mid - 1;  }  }  return res;   }  static void Main() {  int[] arr = {1, 2, 8, 10, 10, 12, 19};  int x = 3;  int index = CeilSearch(arr, x);    if (index == -1)   Console.WriteLine($"Ceiling of {x} doesn't exist in array");  else  Console.WriteLine($"Ceiling of {x} is {arr[index]}");  } }

JavaScript

// Function to find the ceiling of x using // binary search function ceilSearch(arr, x) {  let lo = 0, hi = arr.length - 1, res = -1;    while (lo <= hi) {  let mid = Math.floor(lo + (hi - lo) / 2);  if (arr[mid] < x)  lo = mid + 1;     else { // Potential ceiling found  res = mid;   hi = mid - 1;  }  }  return res;  } const arr = [1, 2, 8, 10, 10, 12, 19]; const x = 3; const index = ceilSearch(arr, x);   if (index === -1)   console.log(`Ceiling of ${x} doesn't exist in array`); else  console.log(`Ceiling of ${x} is ${arr[index]}`);

Output

Ceiling of 3 is 8

Using Library Methods

We can use the following library methods in different languages.

The lower_bound() method in C++, Arrays.binarySearch() in Java and bisect_left() in Python

C++

#include <bits/stdc++.h> using namespace std; int main() {  vector<int> arr = { 1, 2, 8, 10, 10, 12, 19 };  int n = arr.size();  int x = 8;  auto itr = lower_bound(arr.begin(), arr.end(),x); // returns iterator  int idx = itr - arr.begin(); // converting to index;  if (idx == n) {  cout << "Ceil Element does not exist " << endl;  }  else {  cout << "Ceil Element of " << x << " is " << arr[idx] << endl;  }  return 0; }

Java

import java.util.Arrays; class GFG {  public static void main(String[] args)  {  int[] arr = { 1, 2, 8, 10, 10, 12, 19 };  int n = arr.length;  int x = 8;  // Use binary search to find the index of the  // ceiling element  int idx = Arrays.binarySearch(arr, x);  if (idx < 0) {  idx = Math.abs(idx) - 1;  }  // Checking if idx is valid  if (idx == n) {  System.out.println(  "Ceiling Element does not exist");  }  else {  System.out.println("Ceiling Element of " + x  + " is " + arr[idx]);  }  } } // This code is contributed by phasing17

Python

from bisect import bisect_left arr = [1, 2, 8, 10, 10, 12, 19] n = len(arr) x = 8 # Use bisect to get ceiling element idx = bisect_left(arr, x) # Checking if idx is valid if idx == n: print("Ceil Element does not exist") else: print(f"Ceil Element of {x} is {arr[idx]}")

using System; public class GFG {  public static void Main(string[] args)  {  int[] arr = { 1, 2, 8, 10, 10, 12, 19 };  int n = arr.Length;  int x = 8;  // Use Array.BinarySearch to find the index of the  // ceiling element  int idx = Array.BinarySearch(arr, x);  if (idx < 0) {  idx = Math.Abs(idx) - 1;  }  // Checking if idx is valid  if (idx == n) {  Console.WriteLine(  "Ceiling Element does not exist");  }  else {  Console.WriteLine("Ceiling Element of " + x  + " is " + arr[idx]);  }  } } // This code is contributed by Prasad Kandekar(prasad264)

JavaScript

const arr = [1, 2, 8, 10, 10, 12, 19]; const n = arr.length; const x = 8; // Use the Array.findIndex() method to find the index of the // first element that is greater than or equal to x let idx = arr.findIndex(val => val >= x); // Checking if idx is valid if (idx === -1) {  console.log("Ceiling Element does not exist"); }  else {  console.log(`Ceiling Element of ${x} is ${arr[idx]}`); } // This code is contributed by Prasad Kandekar(prasad264)