ronith
6/7/2018 - 7:13 AM

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, 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

Ceiling in a sorted array - linear search.cpp
content_copyfile_download
#include<iostream>
using namespace std;

int main(){
    int n,x;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>x;

    if(x<a[0])//use exit() at each line to terminate when found the answer.
        cout<< "floor doesn't exist in array,  ceil is "<<a[0];
    if (x>a[n-1])
        cout<< "floor is "<<a[n-1]<< ",  ceil doesn't exist in array";

    if (a[n-1] == x)
            cout<< "floor is " << a[n-1] << ", ceil is " << a[n-1];

    for(int i=0;i<n-1;i++){
        if (a[i] == x){
            cout<< "floor is " << a[i] << ", ceil is " << a[i];
            break;
        }
        if (a[i] < x && a[i+1] > x){
            cout<< "floor is " << a[i] << ", ceil is " << a[i+1];
            break;
        }
    }
}