Ceiling in a sorted array

Last Updated : 10 Feb, 2023

Given a sorted array and a value x, the ceiling of x is the smallest element in an array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume that the array is sorted in non-decreasing order. Write efficient functions to find the floor and ceiling of x.
Examples :

For example, let the input array be {1, 2, 8, 10, 10, 12, 19}
For x = 0:    floor doesn't exist in array,  ceil  = 1
For x = 1:    floor  = 1,  ceil  = 1
For x = 5:    floor  = 2,  ceil  = 8
For x = 20:   floor  = 19,  ceil doesn't exist in array

In the below methods, we have implemented only ceiling search functions. Floor search can be implemented in the same way.

Method 1 (Linear Search)
Algorithm to search ceiling of x:

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.

Below is the implementation of the above approach:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
/* Function to get index of ceiling of x in arr[low..high] */
int ceilSearch(int arr[], int low, int high, int x) 
{ 
     
    int i; 
     
    /* If x is smaller than or equal to first element, 
        then return the first element */
    if(x <= arr[low]) 
        return low; 
     
    /* Otherwise, linearly search for ceil value */
    for(i = low; i < high; 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, 0, n-1, x); 
    if(index == -1) 
        cout << "Ceiling of " << x << " doesn't exist in array "; 
    else
        cout << "ceiling of " << x << " is " << arr[index]; 
     
    return 0; 
} 
 
// This is code is contributed by rathbhupendra

C

#include<stdio.h>
 
/* Function to get index of ceiling of x in arr[low..high] */
int ceilSearch(int arr[], int low, int high, int x)
{
  int i;    
 
  /* If x is smaller than or equal to first element,
    then return the first element */
  if(x <= arr[low])
    return low;  
 
  /* Otherwise, linearly search for ceil value */
  for(i = low; i < high; 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 program to check above functions */
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, 0, n-1, x);
   if(index == -1)
     printf("Ceiling of %d doesn't exist in array ", x);
   else
     printf("ceiling of %d is %d", x, arr[index]);
   getchar();
   return 0;
}

Java

class Main
{
    /* Function to get index of ceiling 
       of x in arr[low..high] */
    static int ceilSearch(int arr[], int low, int high, int x)
    {
      int i;    
      
      /* If x is smaller than or equal to first 
         element,then return the first element */
      if(x <= arr[low])
        return low;  
      
      /* Otherwise, linearly search for ceil value */
      for(i = low; i < high; 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 program to check above functions */
    public static void main (String[] args)
    {
       int arr[] = {1, 2, 8, 10, 10, 12, 19};
       int n = arr.length;
       int x = 3;
       int index = ceilSearch(arr, 0, n-1, 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]);
    }  
}

Python3

# Function to get index of ceiling of x in arr[low..high] */
def ceilSearch(arr, low, high, x):
 
    # If x is smaller than or equal to first element,
    # then return the first element */
    if x <= arr[low]:
        return low
 
    # Otherwise, linearly search for ceil value */
    i = low
    for i in range(high):
        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 program to check above functions */
arr = [1, 2, 8, 10, 10, 12, 19]
n = len(arr)
x = 3
index = ceilSearch(arr, 0, n-1, x);
 
if index == -1:
    print ("Ceiling of %d doesn't exist in array "% x)
else:
    print ("ceiling of %d is %d"%(x, arr[index]))
 
# This code is contributed by Shreyanshi Arun

C#

// C# program to find ceiling
// in a sorted array
using System;
 
class GFG {
     
    // Function to get index of ceiling 
    // of x in arr[low..high] 
    static int ceilSearch(int[] arr, int low, 
                           int high, int x)
    {
        int i;
 
        // If x is smaller than or equal
        // to first element, then return
        // the first element 
        if (x <= arr[low])
            return low;
 
        // Otherwise, linearly search 
        // for ceil value 
        for (i = low; i < high; 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()
    {
        int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
        int n = arr.Length;
        int x = 3;
        int index = ceilSearch(arr, 0, n - 1, x);
         
        if (index == -1)
            Console.Write("Ceiling of " + x +
                     " doesn't exist in array");
        else
            Console.Write("ceiling of " + x +
                         " is " + arr[index]);
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// Function to get index of 
// ceiling of x in arr[low..high] 
function ceilSearch($arr, $low, $high, $x)
{
 
    // If x is smaller than or equal 
    // to first element, then return 
    // the first element 
    if($x <= $arr[$low])
        return $low; 
     
    // Otherwise, linearly search
    // for ceil value 
    for($i = $low; $i < $high; $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
$arr = array(1, 2, 8, 10, 10, 12, 19);
$n = sizeof($arr);
$x = 3;
$index = ceilSearch($arr, 0, $n - 1, $x);
if($index == -1)
    echo("Ceiling of " . $x . 
         " doesn't exist in array ");
else
    echo("ceiling of " . $x . " is " . 
                        $arr[$index]);
 
// This code is contributed by Ajit.
?>

Javascript

<script>
 
/* Function to get index of ceiling of 
x in arr[low..high] */
function ceilSearch(arr, low, high, x) 
{ 
     
    let i; 
     
    /* If x is smaller than or equal to first element, 
        then return the first element */
    if(x <= arr[low]) 
        return low; 
     
    /* Otherwise, linearly search for ceil value */
    for(i = low; i < high; 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 
 
    let arr = [1, 2, 8, 10, 10, 12, 19]; 
    let n = arr.length; 
    let x = 3; 
    let index = ceilSearch(arr, 0, n-1, x); 
    if(index == -1) 
        document.write("Ceiling of " + x + " doesn't exist in array "); 
    else
        document.write ("ceiling of " + x + " is " + arr[index]);  
 
 
</script>

Output

ceiling of 3 is 8

Time Complexity: O(n),
Auxiliary Space: O(1)

Method 2 (Binary Search)

Instead of using linear search, binary search is used here to find out the index. Binary search reduces the time complexity to O(Logn).

C++

#include <bits/stdc++.h>
using namespace std;
 
/* Function to get index of
   ceiling of x in arr[low..high]*/
int ceilSearch(int arr[], int low, int high, int x)
{
    int mid;
 
    /* If x is smaller than
       or equal to the first element,
       then return the first element */
    if (x <= arr[low])
        return low;
 
    /* If x is greater than the last element,
       then return -1 */
    if (x > arr[high])
        return -1;
 
    /* get the index of middle element of arr[low..high]*/
    mid = (low + high) / 2; /* low + (high - low)/2 */
 
    /* If x is same as middle element,
       then return mid */
    if (arr[mid] == x)
        return mid;
 
    /* If x is greater than arr[mid],
       then either arr[mid + 1] is ceiling of x
       or ceiling lies in arr[mid+1...high] */
    else if (arr[mid] < x) {
        if (mid + 1 <= high && x <= arr[mid + 1])
            return mid + 1;
        else
            return ceilSearch(arr, mid + 1, high, x);
    }
 
    /* If x is smaller than arr[mid],
       then either arr[mid] is ceiling of x
       or ceiling lies in arr[low...mid-1] */
    else {
        if (mid - 1 >= low && x > arr[mid - 1])
            return mid;
        else
            return ceilSearch(arr, low, mid - 1, x);
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 20;
    int index = ceilSearch(arr, 0, n - 1, x);
    if (index == -1)
        cout << "Ceiling of " << x
             << " doesn't exist in array ";
    else
        cout << "ceiling of " << x << " is " << arr[index];
 
    return 0;
}
 
// This code is contributed by rathbhupendra

C

#include <stdio.h>
 
/* Function to get index of ceiling of x in arr[low..high]*/
int ceilSearch(int arr[], int low, int high, int x)
{
    int mid;
 
    /* If x is smaller than or equal to the first element,
      then return the first element */
    if (x <= arr[low])
        return low;
 
    /* If x is greater than the last element, then return -1
     */
    if (x > arr[high])
        return -1;
 
    /* get the index of middle element of arr[low..high]*/
    mid = (low + high) / 2; /* low + (high - low)/2 */
 
    /* If x is same as middle element, then return mid */
    if (arr[mid] == x)
        return mid;
 
    /* If x is greater than arr[mid], then either arr[mid +
      1] is ceiling of x or ceiling lies in
      arr[mid+1...high] */
    else if (arr[mid] < x) {
        if (mid + 1 <= high && x <= arr[mid + 1])
            return mid + 1;
        else
            return ceilSearch(arr, mid + 1, high, x);
    }
 
    /* If x is smaller than arr[mid], then either arr[mid]
       is ceiling of x or ceiling lies in arr[low...mid-1]
     */
    else {
        if (mid - 1 >= low && x > arr[mid - 1])
            return mid;
        else
            return ceilSearch(arr, low, mid - 1, x);
    }
}
 
/* Driver program to check above functions */
int main()
{
    int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 20;
    int index = ceilSearch(arr, 0, n - 1, x);
    if (index == -1)
        printf("Ceiling of %d doesn't exist in array ", x);
    else
        printf("ceiling of %d is %d", x, arr[index]);
    getchar();
    return 0;
}

Java

import java.util.Arrays;
 
public class CeilSearch {
 
    // Function to get index of ceiling of x in arr[low..high]
    public static int ceilSearch(int[] arr, int low, int high, int x) {
        int mid;
 
        /* If x is smaller than or equal to the first element,
           then return the first element */
        if (x <= arr[low])
            return low;
 
        /* If x is greater than the last element,
           then return -1 */
        if (x > arr[high])
            return -1;
 
        /* get the index of middle element of arr[low..high]*/
        mid = (low + high) / 2; /* low + (high - low)/2 */
 
        /* If x is same as middle element,
           then return mid */
        if (arr[mid] == x)
            return mid;
 
        /* If x is greater than arr[mid],
           then either arr[mid + 1] is ceiling of x
           or ceiling lies in arr[mid+1...high] */
        else if (arr[mid] < x) {
            if (mid + 1 <= high && x <= arr[mid + 1])
                return mid + 1;
            else
                return ceilSearch(arr, mid + 1, high, x);
        }
 
        /* If x is smaller than arr[mid],
           then either arr[mid] is ceiling of x
           or ceiling lies in arr[low...mid-1] */
        else {
            if (mid - 1 >= low && x > arr[mid - 1])
                return mid;
            else
                return ceilSearch(arr, low, mid - 1, x);
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 2, 8, 10, 10, 12, 19};
        int n = arr.length;
        int x = 20;
        int index = ceilSearch(arr, 0, n - 1, 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]);
    }
}

Python3

# Function to get index of ceiling of x in arr[low..high]*/
def ceilSearch(arr, low, high, x):
 
    # If x is smaller than or equal to the first element,
    # then return the first element */
    if x <= arr[low]:
        return low 
 
    # If x is greater than the last element, then return -1 */
    if x > arr[high]:
        return -1 
  
    # get the index of middle element of arr[low..high]*/
    mid = (low + high)/2;  # low + (high - low)/2 */
  
    # If x is same as middle element, then return mid */
    if arr[mid] == x:
        return mid
 
    # If x is greater than arr[mid], then either arr[mid + 1]
    # is ceiling of x or ceiling lies in arr[mid+1...high] */ 
    elif arr[mid] < x:
        if mid + 1 <= high and x <= arr[mid+1]:
            return mid + 1
        else:
            return ceilSearch(arr, mid+1, high, x)
  
    # If x is smaller than arr[mid], then either arr[mid] 
    # is ceiling of x or ceiling lies in arr[low...mid-1] */   
    else:
        if mid - 1 >= low and x > arr[mid-1]:
            return mid
        else:
            return ceilSearch(arr, low, mid - 1, x)
  
# Driver program to check above functions
arr = [1, 2, 8, 10, 10, 12, 19]
n = len(arr)
x = 20
index = ceilSearch(arr, 0, n-1, x);
 
if index == -1:
    print ("Ceiling of %d doesn't exist in array "% x)
else:
    print ("ceiling of %d is %d"%(x, arr[index]))
 
# This code is contributed by Shreyanshi Arun

C#

// C# program to find ceiling
// in a sorted array
 
using System;
 
class GFG {
 
    // Function to get index of ceiling
    // of x in arr[low..high]
    static int ceilSearch(int[] arr, int low, int high,
                          int x)
    {
        int mid;
 
        // If x is smaller than or equal
        // to the first element, then
        // return the first element.
        if (x <= arr[low])
            return low;
 
        // If x is greater than the last
        // element, then return -1
        if (x > arr[high])
            return -1;
 
        // get the index of middle
        // element of arr[low..high]
        mid = (low + high) / 2;
        // low + (high - low)/2
 
        // If x is same as middle
        // element then return mid
        if (arr[mid] == x)
            return mid;
 
        // If x is greater than arr[mid],
        // then either arr[mid + 1] is
        // ceiling of x or ceiling lies
        // in arr[mid+1...high]
        else if (arr[mid] < x) {
            if (mid + 1 <= high && x <= arr[mid + 1])
                return mid + 1;
            else
                return ceilSearch(arr, mid + 1, high, x);
        }
 
        // If x is smaller than arr[mid],
        // then either arr[mid] is ceiling
        // of x  or ceiling lies in
        // arr[low...mid-1]
        else {
            if (mid - 1 >= low && x > arr[mid - 1])
                return mid;
            else
                return ceilSearch(arr, low, mid - 1, x);
        }
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
        int n = arr.Length;
        int x = 20;
        int index = ceilSearch(arr, 0, n - 1, x);
        if (index == -1)
            Console.Write("Ceiling of " + x
                          + " doesn't exist in array");
        else
            Console.Write("ceiling of " + x + " is "
                          + arr[index]);
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// PHP Program for Ceiling in 
// a sorted array
 
// Function to get index of ceiling
// of x in arr[low..high]
function ceilSearch($arr, $low, 
                    $high, $x)
{
    $mid; 
     
    /* If x is smaller than or 
       equal to the first element,
       then return the first element */
    if($x <= $arr[$low])
        return $low; 
     
    /* If x is greater than the
       last element, then return
       -1 */
    if($x > $arr[$high])
        return -1; 
     
    /* get the index of middle
       element of arr[low..high] */
    // low + (high - low)/2
    $mid = ($low + $high)/2; 
     
    /* If x is same as middle element,
       then return mid */
    if($arr[$mid] == $x)
        return $mid;
         
    /* If x is greater than arr[mid],
       then either arr[mid + 1]    is 
       ceiling of x or ceiling lies 
       in arr[mid+1...high] */
    else if($arr[$mid] < $x)
    {
        if($mid + 1 <= $high && 
           $x <= $arr[$mid + 1])
            return $mid + 1;
        else
            return ceilSearch($arr, $mid + 1, 
                              $high, $x);
    }
     
    /* If x is smaller than arr[mid],
       then either arr[mid] is ceiling
       of x or ceiling lies in 
       arr[low....mid-1] */
    else
    {
        if($mid - 1 >= $low && 
           $x > $arr[$mid - 1])
            return $mid;
        else
         return ceilSearch($arr, $low, 
                           $mid - 1, $x);
    }
}
 
// Driver Code
$arr = array(1, 2, 8, 10, 10, 12, 19);
$n = sizeof($arr);
$x = 20;
$index = ceilSearch($arr, 0, $n - 1, $x);
if($index == -1)
    echo("Ceiling of $x doesn't exist in array ");
else
    echo("ceiling of $x is"); 
    echo(isset($arr[$index]));
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
// Javascript Program for Ceiling in  
// a sorted array 
   
// Function to get index of ceiling 
// of x in arr[low..high] 
function ceilSearch(arr, low, high, x) 
{ 
    let mid;  
       
    /* If x is smaller than or  
       equal to the first element, 
       then return the first element */
    if(x <= arr[low]) 
        return low;  
       
    /* If x is greater than the 
       last element, then return 
       -1 */
    if(x > arr[high]) 
        return -1;  
       
    /* get the index of middle 
       element of arr[low..high] */
    // low + (high - low)/2 
    mid = (low + high)/2;  
       
    /* If x is same as middle element, 
       then return mid */
    if(arr[mid] == x) 
        return mid; 
           
    /* If x is greater than arr[mid], 
       then either arr[mid + 1]    is  
       ceiling of x or ceiling lies  
       in arr[mid+1...high] */
    else if(arr[mid] < x) 
    { 
        if(mid + 1 <= high && x <= arr[mid + 1]) 
            return mid + 1; 
        else
            return ceilSearch(arr, mid + 1, high, x); 
    } 
       
    /* If x is smaller than arr[mid], 
       then either arr[mid] is ceiling 
       of x or ceiling lies in  
       arr[low....mid-1] */
    else
    { 
        if(mid - 1 >= low && x > arr[mid - 1]) 
          return mid; 
        else
         return ceilSearch(arr, low, mid - 1, x); 
    } 
} 
   
// Driver Code 
let arr = [1, 2, 8, 10, 10, 12, 19]; 
let n = arr.length; 
let x = 20; 
let index = ceilSearch(arr, 0, n - 1, x); 
 
if(index == -1){
    document.write(`Ceiling of ${x} doesn't exist in array `); 
}else{
    document.write(`ceiling of ${x} is ${arr[index]}`);  
}
   
// This code is contributed by _saurabh_jaiswal. 
 
</script>

Output

Ceiling of 20 doesn't exist in array

Time Complexity: O(log(n)),
Auxiliary Space: O(1)

Another Implementation of Method 2 :

As like previous method here also binary search is being used but the code logic is different instead of lots of if else check i will simply return and lets understand through below steps :

Step 1 : { low->1, 2, 8, 10<-mid, 10, 12, 19<-high};

if( x < mid) yes set high = mid -1;

Step 2 : { low ->1, 2 <-mid, 8 <-high, 10, 10, 12, 19};

if( x < mid) no set low = mid + 1;

Step 3 : {1, 2, 8<-high,low,mid, 10, 10, 12, 19};

if( x == mid ) yes return mid  
if(x < mid ) no low = mid + 1

Step 4 : {1, 2, 8<-high,mid, 10<-low, 10, 12, 19};

check while(low =<  high)

condition break and return low which is my ceiling of target.

C++

#include <bits/stdc++.h>
using namespace std;
 
/* Function to get index of
       ceiling of x in arr[low..high]*/
int ceilSearch(int arr[], int low, int high, int x)
{
 
    // base condition if length of arr == 0 then return -1
    if (sizeof(arr) / sizeof(arr[0]) == 0) {
        return -1;
    }
    int mid;
 
    // this while loop function will run until condition not
    // break once condition break loop will return start and
    // ans is low which will be next smallest greater than
    // target which is ceiling
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (arr[mid] == x)
            return mid;
        else if (x < arr[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
 
/* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
                if( x < mid) yes set high = mid -1;
   step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12,
   19}; if( x < mid) no set low = mid + 1; step 3 : {1, 2, 8
   = high,low,low,  10, 10, 12, 19}; if( x == mid ) yes
   return mid if(x < mid ) no low = mid + 1 step 4  : {1, 2,
   8 = high,mid, 10 = low, 10, 12, 19}; check while(low < =
   high) condition break and return low which will next
   greater of target */
 
/* Driver program to check above functions */
int main()
{
    int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 8;
    int index = ceilSearch(arr, 0, n - 1, x);
    if (index == -1)
        printf("Ceiling of %d does not exist in an array",
               x);
    else
        printf("Ceiling of %d is %d", x, arr[index]);
    return 0;
}

C

#include <stdio.h>
 
// Function to get index of ceiling of x in arr[low..high]
int ceilSearch(int arr[], int low, int high, int x)
{
 
    // base condition if length of arr == 0 then return -1
    if (x == 0) {
        return -1;
    }
    int mid;
 
    // this while loop function will run until condition not
    // break once condition break loop will return start and
    // ans is low which will be next smallest greater than
    // target which is ceiling
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (arr[mid] == x)
            return mid;
        else if (x < arr[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
 
/* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
                if( x < mid) yes set high = mid -1;
   step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12,
   19}; if( x < mid) no set low = mid + 1; step 3 : {1, 2, 8
   = high,low,low,  10, 10, 12, 19}; if( x == mid ) yes
   return mid if(x < mid ) no low = mid + 1 step 4  : {1, 2,
   8 = high,mid, 10 = low, 10, 12, 19}; check while(low < =
   high) condition break and return low which will next
   greater of target */
 
/* Driver program to check above functions */
int main()
{
    int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 8;
    int index = ceilSearch(arr, 0, n - 1, x);
    if (index == -1)
        printf("Ceiling of %d does not exist in an array", x);
    else
        printf("Ceiling of %d is %d", x, arr[index]);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

class Main {
    /* Function to get index of
       ceiling of x in arr[low..high]*/
    static int ceilSearch(int arr[], int low, int high,
                          int x)
    {
        // base condition if length of arr == 0 then return
        // -1
        if (x == 0) {
            return -1;
        }
        /* this while loop function will run until condition
         not break once condition break loop will return
         start and ans is low which will be next smallest
         greater than target which is ceiling*/
        while (low <= high) {
            int mid
                = low + (high - low) / 2; // calculate mid
 
            if (x == arr[mid]) {
                return mid;
            }
            if (x < arr[mid]) {
                high = mid - 1;
            }
 
            else {
                low = mid + 1;
            }
        }
        return low;
    }
    /* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
              if( x < mid) yes set high = mid -1;
    step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12, 19};
              if( x < mid) no set low = mid + 1;
    step 3 : {1, 2, 8 = high,low,low,  10, 10, 12, 19};
               if( x == mid ) yes return mid
               if(x < mid ) no low = mid + 1
    step 4  : {1, 2, 8 = high,mid, 10 = low, 10, 12, 19};
              check while(low < = high)
               condition break and return low which will
    next greater of target */
 
    /* Driver program to check above functions */
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
        int n = arr.length;
        int x = 8;
        int index = ceilSearch(arr, 0, n - 1, 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]);
    }
}

Python3

# Function to get index of ceiling of x in arr[low..high]
def ceilSearch(arr, low, high, x):
 
  # base condition if length of arr == 0 then return -1
    if (x == 0):
        return -1
 
    """this while loop function will run until
  condition not break once condition break
       loop will return start and ans is low
       which will be next smallest greater than target
       which is ceiling"""
    while (low <= high):
        mid = low + (high - low) / 2
        mid = int(mid)
        if (arr[mid] == x):
            return mid
        elif (x < arr[mid]):
            high = mid - 1
        else:
            low = mid + 1
 
    return low
 
 
""" step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high}; 
                if( x < mid) yes set high = mid -1;
      step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12, 19};
                if( x < mid) no set low = mid + 1;
      step 3 : {1, 2, 8 = high,low,low,  10, 10, 12, 19};
                 if( x == mid ) yes return mid 
                 if(x < mid ) no low = mid + 1
      step 4  : {1, 2, 8 = high,mid, 10 = low, 10, 12, 19};
                check while(low < = high)
                 condition break and return low which will next greater of target """
 
# Driver program to check above functions
arr = [1, 2, 8, 10, 10, 12, 19]
n = len(arr)
x = 8
index = ceilSearch(arr, 0, n - 1, x)
if (index == -1):
    print("Ceiling of", x, "does not exist in an array")
else:
    print("Ceiling of", x, "is", arr[index])

C#

// C# program for the above approach
 
using System;
class GFG
{
  /* Function to get index of 
       ceiling of x in arr[low..high]*/
  static int ceilSearch(int[] arr, int low, int high, int x)
  {
    // base condition if length of arr == 0 then return -1
    if (x == 0)
    {
      return -1;
    }
    /* this while loop function will run until condition not break once condition break
         loop will return start and ans is low which will be next smallest greater than target
         which is ceiling*/
    while (low <= high)
    {
      int mid = low + (high - low) / 2;//calculate mid
 
      if (x == arr[mid])
      {
        return mid;
      }
      if (x < arr[mid])
      {
        high = mid - 1;
      }
 
      else
      {
        low = mid + 1;
      }
    }
    return low;
    /* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high}; 
                  if( x < mid) yes set high = mid -1;
        step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12, 19};
                  if( x < mid) no set low = mid + 1;
        step 3 : {1, 2, 8 = high,low,low,  10, 10, 12, 19};
                   if( x == mid ) yes return mid 
                   if(x < mid ) no low = mid + 1
        step 4  : {1, 2, 8 = high,mid, 10 = low, 10, 12, 19};
                  check while(low < = high)
                   condition break and return low which will next greater of target */
 
  }
   
  /* Driver program to check above functions */
  public static void Main()
  {
    int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
    int n = arr.Length;
    int x = 8;
    int index = ceilSearch(arr, 0, n - 1, x);
    if (index == -1)
      Console.WriteLine("Ceiling of " + x + " doesn't exist in array");
    else
      Console.WriteLine("ceiling of " + x + " is " + arr[index]);
  }
}

Javascript

//JS program to implement the approach
 
/* Function to get index of 
       ceiling of x in arr[low..high]*/
function ceilSearch(arr, low, high, x)
{
 
  // base condition if length of arr == 0 then return -1
  if (x == 0)
  {
    return -1;
  }
  var mid;
 
  /* this while loop function will run until 
  condition not break once condition break
       loop will return start and ans is low 
       which will be next smallest greater than target
       which is ceiling*/
  while (low <= high)
  {
    mid = low + (high - low) / 2;
    if (arr[mid] == x)
    {
      return mid;
    }
    else if (x < arr[mid])
    {
 
      high = mid - 1;
    }
    else
    {
 
      low = mid + 1;
    }
 
  }
  return low;
}
 
/* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high}; 
                if( x < mid) yes set high = mid -1;
      step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12, 19};
                if( x < mid) no set low = mid + 1;
      step 3 : {1, 2, 8 = high,low,low,  10, 10, 12, 19};
                 if( x == mid ) yes return mid 
                 if(x < mid ) no low = mid + 1
      step 4  : {1, 2, 8 = high,mid, 10 = low, 10, 12, 19};
                check while(low < = high)
                 condition break and return low which will next greater of target */
 
/* Driver program to check above functions */
var arr = [1, 2, 8, 10, 10, 12, 19];
var n = arr.length;
var x = 8;
var index = ceilSearch(arr, 0, n - 1, x);
  if (index == -1)
  {
    console.log("Ceiling of " + x + " does not exist in an array");
  }
  else
  {
    console.log("Ceiling of " + x + " is " + arr[index]);
  }

Output

Ceiling of 8 is 8

Time Complexity: O(log(n)), where n is the length of the given array,
Auxiliary Space: O(1)

Method Using C++ STL lower_bound

The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val. This means that the function returns an iterator pointing to the next smallest number just greater than or equal to that number. If there are multiple values that are equal to val, lower_bound() returns the iterator of the first such value.

Simpler and Shorter code :

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

Python3

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]}")

C#

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)

Output

Ceil Element of 8 is 8

Time Complexity: O(log(n)), where n is the length of the given array,
Auxiliary Space: O(1)

https://www.youtube.com/watch?v=Nzm9emAkSCM

Related Articles:

Floor in a Sorted Array
Find floor and ceil in an unsorted array

Please write comments if you find any of the above codes/algorithms incorrect, find better ways to solve the same problem, or want to share code for floor implementation.

GeeksforGeeks

Improve

Previous Article

Find common elements in three sorted arrays

Floor in a Sorted Array

Similar Reads

C Program for Ceiling in a sorted array

Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x. Examples : For example, let the input array be {1, 2, 8

Java Program for Ceiling in a sorted array

Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x. Examples : For example, let the input array be {1, 2, 8

Python3 Program for Ceiling in a sorted array

Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume that the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x. Examples : For example, let the input array be {1, 2, 8

C# Program for Ceiling in a sorted array

Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x. Examples : For example, let the input array be {1, 2, 8

Php Program for Ceiling in a sorted array

Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x. Examples : For example, let the input array be {1, 2, 8

Javascript Program for Ceiling in a sorted array

Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x. Examples : For example, let the input array be {1, 2, 8

C++ Program for Ceiling in a sorted array

Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x. Examples : For example, let the input array be {1, 2, 8

Ceiling in right side for every element in an array

Given an array of integers, find the closest greater element for every element. If there is no greater element then print -1 Examples: Input : arr[] = {10, 5, 11, 10, 20, 12} Output : 10 10 12 12 -1 -1 Input : arr[] = {50, 20, 200, 100, 30} Output : 100 30 -1 -1 -1 A simple solution is to run two nested loops. We pick an outer element one by one. F

Ceiling of every element in same array

Given an array of integers, find the closest greater or same element for every element. If all elements are smaller for an element, then print -1 Examples: Input : arr[] = {10, 5, 11, 10, 20, 12} Output : 10 10 12 10 -1 20 Note that there are multiple occurrences of 10, so ceiling of 10 is 10 itself. Input : arr[] = {6, 11, 7, 8, 20, 12} Output : 7

Count number of common elements between a sorted array and a reverse sorted array

Given two arrays consisting of N distinct integers such that the array A[] and B[] are sorted in ascending and descending order respectively, the task is to find the number of values common in both arrays. Examples: Input: A[] = {1, 10, 100}, B[] = {200, 20, 2}Output: 0 Input: A[] = {2, 4, 5, 8, 12, 13, 17, 18, 20, 22, 309, 999}, B[] = {109, 99, 68

Article Tags :

Practice Tags :