## Problem Statement

Given a sorted array and `a` and a value `x`, find the floor of `x` in the array. The floor of `x` is the largest element in the array smaller than or equal to `x`. Output `1` if the floor doesn’t exist.

Example 1

``````Input : a[] = {1, 3, 9, 15, 15, 18, 21}, x = 5
Output : 3
3 is the largest element in the array smaller than or equal to 5.``````

Example 2

``````Input : a[] = {1, 3, 9, 15, 15, 18, 21}, x = 25
Output : 21
21 is the largest element in the array smaller than or equal to 25.``````

Example 3:

``````Input : a[] = {1, 3, 9, 15, 15, 18, 21}, x = 0
Output : -1
Since floor doesn't exist, output is -1.``````

Given that the array is sorted, we can apply binary search to find the floor of the element. Let’s look at the implementation:

``````import java.util.Scanner;

class FloorOfElementInSortedArray {
private static int findFloorBinarySearch(int[] a, int x) {
int n = a.length;
int start = 0;
int end = n-1;

int floor = -1;

while(start <= end) {
int mid = (start+end)/2;

if(x == a[mid]) {
// a[mid] is the floor
return a[mid];
} else if (x < a[mid]) {
end = mid-1;
} else {
// a[mid] is the largest element found so far that is smaller than x. So it is a candidate for the floor of x
floor = a[mid];
start = mid+1;
}
}

return floor;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}
int x = keyboard.nextInt();
keyboard.close();

System.out.printf("Floor(%d) = %d%n", x, findFloorBinarySearch(a, x));
}
}``````
``````# Output
\$ javac FloorOfElementInSortedArray.java
\$ java FloorOfElementInSortedArray
7
1 3 9 15 15 18 21
5
Floor(5) = 3

\$ java FloorOfElementInSortedArray
7
1 3 9 15 15 18 21
25
Floor(25) = 21

\$ FloorOfElementInSortedArray
7
1 3 9 15 15 18 21
0
Floor(0) = -1``````