Q:

# Given a sorted array of integers, find the floor and ceil of given number x in it. The floor and ceil value of a number points to the largest previous or the smallest following integer respectively

Given a sorted array of integers, find the floor and ceil of given number x in it. The floor and ceil value of a number points to the largest previous or the smallest following integer respectively.

Problem description:

The problem wants you to use the knowledge of mathematics as the floor is the value which is the largest integer less than or equal to x and ceil value is the smallest greater than or equal to x. We are required to approach the problem in a way such that the time complexity should change to linear to logarithmic.

Input:

The first line of the input is the T number of test cases. Each test case consists of integer n and x, size of the array, and the element whose floor and ceil value is to be evaluated respectively. Then each of the following lines contains n elements.

Output:

Print the floor and ceil value of the element x.

Examples:

```Input:
T=1
N=5,X=3
1,2,4,5,6

Output:
floor: 2
ceil: 4```

(a) Brute Force Approach:

In this approach we will iterate through the array and simply find the floor and ceil of the element x in O(n) time.

The floor will the largest element smaller than or equal to element x and the ceil will be the smallest element greater than or equal to element x.

Pseudo Code:

```For FLoor:
//initialise some variable
//floor with -1.
floor=-1
//iteratively move through all
//element until some largest element
//greater than equal to x
for i in length(arr[]):
if(arr[i]<=x)
floor=arr[i]//if found some element then assign.
if(arr[i]>x)//if arr[i]>x then break.
break

For Ceil:
//initialise some variable
//ceil with -1.
ceil=-1
//iteratively move through all
//elements until smallest element
//greater than equal to x.
for i in length(arr[]):
if(arr[i]>=x)
ceil=arr[i],break
```

Time Complexity for the above approach in the worst case is: O(n)

Space Complexity for the above approach in the worst case is: O(1)

b) Binary Search Approach:

In this approach, we will use the concept of binary search to solve the problem. We will find the mid and then recur for the left or right side of the mid index according to the comparison.

Pseudo Code:

```FOR CEIL:
start and end are the range end points.
//initialise ceil with -1.
ceil=-1
CEIL(arr[],start,end):
->  if x is equal to mid element then return mid element.
->  if x is less than the mid element then ceil of the
element x lies in left half of the range i.e in
arr[start,mid], so we will change our celi value
to mid element and search in left half arr[start,mid-1].
->  if x is greater than the mid element then ceil of the
element x lies in the right half of the range i.e in  arr[mid+1,end].

FOR FLOOR:
start and end are the range end points.
//initialise floor with -1.
floor=-1

FLOOR(arr[],start,end):
->  if x is equal to mid element then return mid element
->  if x is less than mid element then floor lies in
the left half of the range i.e arr[start,mid]
->  if x is greater than the mid element then floor lies
in the right half of the range i.e
arr[mid,end],assign floor equal to mid.
The floor lies in arr[mid+1,end] half.
```

Time Complexity for the above approach in the worst case is: O(log(n))

Space Complexity for the above approach in the worst case is: O(1)

C++ Implementation (Brute Force Approach):

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

typedef long long ll;

int main()
{
ll t;
cout << "Enter number of test cases: ";
cin >> t;

while (t--) {
ll n, x;

cout << "Enter N and X: ";
cin >> n >> x;

ll arr[n];

cout << "Enter array elements: ";
for (ll i = 0; i < n; i++)
cin >> arr[i];

ll ceil, floor;

ceil = -1;
floor = -1;

//iterate through all elements
//find largest element smaller than
//equal to x.
for (ll i = 0; i < n; i++) {
if (arr[i] <= x) {
floor = arr[i];
}
else //if element found then break.
break;
}

//iterate through all elements
//find smallest element greater than
//equal to x.
for (ll i = 0; i < n; i++) {
if (arr[i] >= x) {
ceil = arr[i];
break; //break since we no need to
//find any more element as
//array is sorted.
}
}
cout << "Floor:" << floor << " ";
cout << "Ceil:" << ceil << "\n";
}

return 0;
}
``````

Output:

```Enter number of test cases: 3
Enter N and X: 5 3
Enter array elements: 1 2 3 4 5
Floor:3 Ceil:3
Enter N and X: 6 2
Enter array elements: 1 3 3 4 5 6
Floor:1 Ceil:3
Enter N and X: 4 7
Enter array elements: 3 6 8 8
Floor:6 Ceil:8
```

C++ Implementation (Binary Search Approach):

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

typedef long long ll;

int main()
{
ll t;

cout << "Enter number of test cases: ";
cin >> t;

while (t--) {
ll n, x;

cout << "Enter N and X: ";
cin >> n >> x;

ll arr[n];

cout << "Enter array elements: ";
for (ll i = 0; i < n; i++)
cin >> arr[i];

ll ceil, floor;

//initialize floor and ceil with -1.
ceil = -1;
floor = -1;

//start index for binary search.
ll l = 0;

//end index for binary search.
ll r = n - 1;

//perform binary search.
while (l <= r) {
//mid index.
ll mid = l + (r - l) / 2;

//if found then assign and break.
if (arr[mid] == x) {
floor = arr[mid];
break;
}

//if x< mid element then search
//left half range arr[l,mid-1].
if (arr[mid] > x) {
r = mid - 1;
}

//if x> mid element then search
//right half range arr[mid+1,r].
if (x > arr[mid]) {
//since we are findin floor we need
//to update the left floor each time.
floor = arr[mid];
l = mid + 1;
}
}

//reinitialise.
l = 0;
r = n - 1;

//perform binary search again.
while (l <= r) {
//mid index.
ll mid = l + (r - l) / 2;
//if mid element equal to x
//then break from loop.
if (arr[mid] == x) {
//assign ceil.
ceil = arr[mid];
break;
}
//if x<arr[mid] then search in left
//half range [l,mid-1]
if (arr[mid] > x) {
//assign each time ceil value as
//search space is reducing.
ceil = arr[mid];
r = mid - 1;
}
if (arr[mid] < x) {
l = mid + 1;
}
}
cout << "Floor:" << floor << " ";
cout << "Ceil:" << ceil << "\n";
}

return 0;
}
``````

Output:

```Enter number of test cases: 3
Enter N and X: 5 3
Enter array elements: 1 4 6 8 9
Floor:1 Ceil:4
Enter N and X: 6 2
Enter array elements: 1 3 4 5 6 7
Floor:1 Ceil:3
Enter N and X: 3 2
Enter array elements: 3 5 7
Floor:-1 Ceil:3```