Floor and Ceiling in a sorted array

FLOOR
Given a sorted array and a value xfind floor of x. floor of x is the largest element in array smaller than or equal to x.
Example :
Input 
arr = { 1, 2, 4, 6, 10, 12, 14 }
x = 7
Output
3
Element 6(arr[3]) is floor of 7
Discussion :

int getFloor(int arr[],int l,int h,int x){
 if(l<=h){ 
   int mid=(l+h)/2;
   if(arr[mid]>x)return getFloor(arr,l,mid-1,x);
   if(arr[mid]<x && mid+1<=h && arr[mid+1]<=x)return getFloor(arr,mid+1,h,x);
   return mid;
 }
 return -1;
}


CEILING
Given a sorted array and a value xfind ceiling of x. the ceiling of x is the smallest element in array greater than or equal to x
Example :
Input 
arr = { 1, 2, 4, 6, 10, 12, 14 }
x = 7
Output
4
Element 10(arr[4]) is ceiling of 7
Discussion :

int getCeiling(int arr[],int l,int h,int x){
 if(l<=h){ 
   int mid=(l+h)/2;
   if(arr[mid]>x && mid>0 && arr[mid-1]>=x)return getCeiling(arr,l,mid-1,x);
   if(arr[mid]<x)return getCeiling(arr,mid+1,h,x);
   return mid;
 }
 return -1;
}


Comments

Popular posts from this blog

Longest Subarray with Sum greater than Equal to K

Search in Rotated Sorted Array

Consistent Hashing