How to Find the ceiling in a sorted array in C++

In this tutorial, we will find the ceiling in a sorted array in C++. Here, we will have an array and a number y and we have to get ceiling of the number.

Moreover, the ceiling of y is the smallest element in the array that is greater than or equal to y, and the floor is the greatest element that is smaller than or equal to y. Let’s assume the array is in increasing order.

For Example:

  • Given array= {1, 3, 7, 8, 10, 15, 17}
  • And the number is 3
  • Here, the ceiling of number is the smallest element in the array that is greater than or equal to the number.
  • The output: 3

Approach:

LINEAR SEARCH

  • Here is the linear search algorithm to find the ceiling.
  •  Firstly, check if the number y is smaller than or equal to the first element in the array, then we will return the index number of the first element.
  • Else we will linearly search for the index number until the number y lies between arr[i] and arr[i+1].
  • Finally, if we don’t get an index in the last step, then we will print ” not found”.
  • Hence, it is a linear search, so the time complexity is O(n).

So this is how we had found a ceiling of the number. In the same way, we can find the floor of the number.

You may also like:
Interpolation Search Algorithm In C++

 

Find the ceiling in a sorted array in C++

Hence, below is the implementation of the linear search algorithm.

//  implementation 
#include<iostream>
#include <bits/stdc++.h> 
using namespace std; 

// get index 
int ceilingls(int arr[], int lw, int hh, int y) 
{ 
  
   
  int i;
  //If x is smaller than or equal lower element, then return lw 
  if(y <= arr[lw]) 
    return lw; 
  
  for(int i = lw; i < hh; i++) 
  { 
    if(arr[i] == y) 
    return i; 
  
    // if x is bw arr[i] and arr[i+1]
    if(arr[i] < y && arr[i+1] >= y) 
    return i+1; 
  }	 
  
// else return -1
  return -1; 
} 


int main() 
{ 
  int arr[] = {1, 3, 7, 8, 10, 15, 17}; 
  int sn = sizeof(arr)/sizeof(arr[0]); 
  int y = 3; 
  int idx = ceilingls(arr, 0, sn-1, y); 
  if(idx == -1) 
    cout << " doesn't exist "; 
  else
    cout << arr[idx]; 
  
  return 0; 
} 

Output Explanation:

INPUT: {1, 3, 7, 8, 10, 15, 17}
               Y=3
OUTPUT: 3

 

Leave a Reply

Your email address will not be published. Required fields are marked *