Floor and Ceiling in a sorted array
FLOOR
Given a sorted array and a value x. find 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 :
CEILING
Given a sorted array and a value x. find 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 :
Given a sorted array and a value x. find 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 x. find 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
Post a Comment