# Floor in a Sorted Array

Given a sorted array and a value x, the floor of x is the largest element in array smaller than or equal to x. Write efficient functions to find floor of x.

Examples:

```Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 5
Output : 2
2 is the largest element in arr[] smaller than 5.

Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 20
Output : 19
19 is the largest element in arr[] smaller than 20.

Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 0
Output : -1
Since floor doesn't exist, output is -1.
```

Method 1 (Simple)
A simple solution is linearly traverse input sorted array and search for the first element greater than x. The element just before the found element is floor of x.

## C++

 `// C/C++ program to find floor of a given number  ` `// in a sorted array  ` `#include  ` ` `  `/* An inefficient function to get index of floor  ` `of x in arr[0..n-1] */` `int` `floorSearch(``int` `arr[], ``int` `n, ``int` `x)  ` `{  ` `    ``// If last element is smaller than x  ` `    ``if` `(x >= arr[n-1])  ` `        ``return` `n-1;  ` ` `  `    ``// If first element is greater than x  ` `    ``if` `(x < arr)  ` `        ``return` `-1;  ` ` `  `    ``// Linearly search for the first element  ` `    ``// greater than x  ` `    ``for` `(``int` `i=1; i x)  ` `        ``return` `(i-1);  ` ` `  `    ``return` `-1;  ` `}  ` ` `  `/* Driver program to check above functions */` `int` `main()  ` `{  ` `    ``int` `arr[] = {1, 2, 4, 6, 10, 12, 14};  ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr);  ` `    ``int` `x = 7;  ` `    ``int` `index = floorSearch(arr, n-1, x);  ` `    ``if` `(index == -1)  ` `        ``printf``(``"Floor of %d doesn't exist in array "``, x);  ` `    ``else` `        ``printf``(``"Floor of %d is %d"``, x, arr[index]);  ` `    ``return` `0;  ` `}  `

/div>

## Java

 `// Java program to find floor of a given number  ` `// in a sorted array  ` `import` `java.io.*; ` `import` `java.util.*; ` `import` `java.lang.*; ` ` `  `class` `GFG ` `{ ` ` `  `/* An inefficient function to get index of floor  ` `of x in arr[0..n-1] */` `static` `int` `floorSearch(``int` `arr[], ``int` `n, ``int` `x)  ` `{  ` `    ``// If last element is smaller than x  ` `    ``if` `(x >= arr[n-``1``])  ` `        ``return` `n-``1``;  ` ` `  `    ``// If first element is greater than x  ` `    ``if` `(x < arr[``0``])  ` `        ``return` `-``1``;  ` ` `  `    ``// Linearly search for the first element  ` `    ``// greater than x  ` `    ``for` `(``int` `i=``1``; i x)  ` `        ``return` `(i-``1``);  ` ` `  `    ``return` `-``1``;  ` `}  ` ` `  `// Driver Code ` `public` `static` `void` `main(String[] args) ` `{  ` `    ``int` `arr[] = {``1``, ``2``, ``4``, ``6``, ``10``, ``12``, ``14``};  ` `    ``int` `n = arr.length;  ` `    ``int` `x = ``7``;  ` `    ``int` `index = floorSearch(arr, n-``1``, x);  ` `    ``if` `(index == -``1``)  ` `        ``System.out.print(``"Floor of "` `+ x + ``" doesn't exist in array "``);  ` `    ``else` `        ``System.out.print(``"Floor of "` `+ x + ``" is "``+ arr[index]);  ` `}  ` `}  ` ` `  `// This code is contributed  ` `// by Akanksha Rai(Abby_akku) `

## Python3

 `# Python3 program to find floor of a  ` `# given number in a sorted array  ` ` `  `# Function to get index of floor  ` `# of x in arr[low..high]  ` `def` `floorSearch(arr, low, high, x):  ` ` `  `    ``# If low and high cross each other  ` `    ``if` `(low > high):  ` `        ``return` `-``1` ` `  `    ``# If last element is smaller than x  ` `    ``if` `(x >``=` `arr[high]):  ` `        ``return` `high  ` ` `  `    ``# Find the middle point  ` `    ``mid ``=` `int``((low ``+` `high) ``/` `2``)  ` ` `  `    ``# If middle point is floor.  ` `    ``if` `(arr[mid] ``=``=` `x):  ` `        ``return` `mid  ` ` `  `    ``# If x lies between mid-1 and mid  ` `    ``if` `(mid > ``0` `and` `arr[mid``-``1``] <``=` `x  ` `                ``and` `x < arr[mid]):  ` `        ``return` `mid ``-` `1` ` `  `    ``# If x is smaller than mid,  ` `    ``# floor must be in left half.  ` `    ``if` `(x < arr[mid]):  ` `        ``return` `floorSearch(arr, low, mid``-``1``, x)  ` ` `  `    ``# If mid-1 is not floor and x is greater than  ` `    ``# arr[mid],  ` `    ``return` `floorSearch(arr, mid``+``1``, high, x)  ` ` `  ` `  `# Driver Code  ` `arr ``=` `[``1``, ``2``, ``4``, ``6``, ``10``, ``12``, ``14``]  ` `n ``=` `len``(arr)  ` `x ``=` `7` `index ``=` `floorSearch(arr, ``0``, n``-``1``, x)  ` ` `  `if` `(index ``=``=` `-``1``):  ` `    ``print``(``"Floor of"``, x, "doesn't exist ` `                    ``in` `array ``", end = "``")  ` `else``:  ` `    ``print``(``"Floor of"``, x, ``"is"``, arr[index])  ` ` `  `# This code is contributed by Smitha Dinesh Semwal.  `

## PHP

 `= ``\$arr``[``\$n` `- 1])  ` `        ``return` `\$n` `- 1;  ` ` `  `    ``// If first element is greater ` `    ``// than x  ` `    ``if` `(``\$x` `< ``\$arr``)  ` `        ``return` `-1;  ` ` `  `    ``// Linearly search for the  ` `    ``// first element greater than x  ` `    ``for` `(``\$i` `= 1; ``\$i` `< ``\$n``; ``\$i``++)  ` `    ``if` `(``\$arr``[``\$i``] > ``\$x``)  ` `        ``return` `(``\$i` `- 1);  ` ` `  `    ``return` `-1;  ` `}  ` ` `  `// Driver Code ` `\$arr` `= ``array` `(1, 2, 4, 6, 10, 12, 14);  ` `\$n` `= sizeof(``\$arr``);  ` `\$x` `= 7;  ` `\$index` `= floorSearch(``\$arr``, ``\$n` `- 1, ``\$x``);  ` `if` `(``\$index` `== -1)  ` `    ``echo` `"Floor of "` `, ``\$x` `,  ` `         ``"doesn't exist in array "``;  ` `else` `    ``echo` `"Floor of "``, ``\$x``, ` `         ``" is "``, ``\$arr``[``\$index``];  ` `     `  `// This code is contributed by ajit ` `?> `

Output:

```Floor of 7 is 6.
```

Time Complexity : O(n)

Method 2 (Efficient)
The idea is to use Binary Search.

## C++

 `// A C/C++ program to find floor of a given number ` `// in a sorted array ` `#include ` ` `  `/* Function to get index of floor of x in ` `   ``arr[low..high] */` `int` `floorSearch(``int` `arr[], ``int` `low, ``int` `high, ``int` `x) ` `{ ` `    ``// If low and high cross each other ` `    ``if` `(low > high) ` `        ``return` `-1; ` ` `  `    ``// If last element is smaller than x ` `    ``if` `(x >= arr[high]) ` `        ``return` `high; ` ` `  `    ``// Find the middle point ` `    ``int` `mid = (low+high)/2; ` ` `  `    ``// If middle point is floor. ` `    ``if` `(arr[mid] == x) ` `        ``return` `mid; ` ` `  `    ``// If x lies between mid-1 and mid ` `    ``if` `(mid > 0 && arr[mid-1] <= x && x < arr[mid]) ` `        ``return` `mid-1; ` ` `  `    ``// If x is smaller than mid, floor must be in ` `    ``// left half. ` `    ``if` `(x < arr[mid]) ` `        ``return` `floorSearch(arr, low, mid-1, x); ` ` `  `    ``// If mid-1 is not floor and x is greater than ` `    ``// arr[mid], ` `    ``return` `floorSearch(arr, mid+1, high, x); ` `} ` ` `  `/* Driver program to check above functions */` `int` `main() ` `{ ` `    ``int` `arr[] = {1, 2, 4, 6, 10, 12, 14}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``int` `x = 7; ` `    ``int` `index = floorSearch(arr, 0, n-1, x); ` `    ``if` `(index == -1) ` `        ``printf``(``"Floor of %d doesn't exist in array "``, x); ` `    ``else` `        ``printf``(``"Floor of %d is %d"``, x, arr[index]); ` `    ``return` `0; ` `} `

## Java

 `// Java program to find floor of ` `// a given number in a sorted array ` `import` `java.io.*; ` ` `  `class` `GFG { ` `     `  `    ``/* Function to get index of floor of x in ` `    ``arr[low..high] */` `    ``static` `int` `floorSearch(``int` `arr[], ``int` `low,  ` `                            ``int` `high, ``int` `x) ` `    ``{ ` `        ``// If low and high cross each other ` `        ``if` `(low > high) ` `            ``return` `-``1``; ` ` `  `        ``// If last element is smaller than x ` `        ``if` `(x >= arr[high]) ` `            ``return` `high; ` ` `  `        ``// Find the middle point ` `        ``int` `mid = (low+high)/``2``; ` ` `  `        ``// If middle point is floor. ` `        ``if` `(arr[mid] == x) ` `            ``return` `mid; ` ` `  `        ``// If x lies between mid-1 and mid ` `        ``if` `(mid > ``0` `&& arr[mid-``1``] <= x && x < ` `                                    ``arr[mid]) ` `            ``return` `mid-``1``; ` ` `  `        ``// If x is smaller than mid, floor ` `        ``// must be in left half. ` `        ``if` `(x < arr[mid]) ` `            ``return` `floorSearch(arr, low,  ` `                               ``mid - ``1``, x); ` ` `  `        ``// If mid-1 is not floor and x is ` `        ``// greater than arr[mid], ` `        ``return` `floorSearch(arr, mid + ``1``, high, ` `                                         ``x); ` `    ``} ` ` `  `    ``/* Driver program to check above functions */` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `arr[] = {``1``, ``2``, ``4``, ``6``, ``10``, ``12``, ``14``}; ` `        ``int` `n = arr.length; ` `        ``int` `x = ``7``; ` `        ``int` `index = floorSearch(arr, ``0``, n - ``1``,  ` `                                          ``x); ` `        ``if` `(index == -``1``) ` `            ``System.out.println(``"Floor of "` `+ x + ` `                     ``" dosen't exist in array "``); ` `        ``else` `            ``System.out.println(``"Floor of "` `+ x + ` `                            ``" is "` `+ arr[index]); ` `    ``} ` `} ` `// This code is contributed by Prerna Saini `

## Python3

 `# Python3 program to find floor of a   ` `# given number in a sorted array ` ` `  `# Function to get index of floor  ` `# of x in arr[low..high]  ` `def` `floorSearch(arr, low, high, x): ` ` `  `    ``# If low and high cross each other ` `    ``if` `(low > high): ` `        ``return` `-``1` ` `  `    ``# If last element is smaller than x ` `    ``if` `(x >``=` `arr[high]): ` `        ``return` `high ` ` `  `    ``# Find the middle point ` `    ``mid ``=` `int``((low ``+` `high) ``/` `2``) ` ` `  `    ``# If middle point is floor. ` `    ``if` `(arr[mid] ``=``=` `x): ` `        ``return` `mid ` ` `  `    ``# If x lies between mid-1 and mid ` `    ``if` `(mid > ``0` `and` `arr[mid``-``1``] <``=` `x  ` `                ``and` `x < arr[mid]): ` `        ``return` `mid ``-` `1` ` `  `    ``# If x is smaller than mid,   ` `    ``# floor must be in left half. ` `    ``if` `(x < arr[mid]): ` `        ``return` `floorSearch(arr, low, mid``-``1``, x) ` ` `  `    ``# If mid-1 is not floor and x is greater than ` `    ``# arr[mid], ` `    ``return` `floorSearch(arr, mid``+``1``, high, x) ` ` `  ` `  `# Driver Code ` `arr ``=` `[``1``, ``2``, ``4``, ``6``, ``10``, ``12``, ``14``] ` `n ``=` `len``(arr) ` `x ``=` `7` `index ``=` `floorSearch(arr, ``0``, n``-``1``, x) ` ` `  `if` `(index ``=``=` `-``1``): ` `    ``print``(``"Floor of"``, x, "doesn't exist ` `                    ``in` `array ``", end = "``") ` `else``: ` `    ``print``(``"Floor of"``, x, ``"is"``, arr[index]) ` ` `  `# This code is contributed by Smitha Dinesh Semwal. `

## C#

 `// C# program to find floor of ` `// a given number in a sorted array ` `using` `System; ` `  `  `class` `GFG { ` `      `  `    ``/* Function to get index of floor of x in ` `    ``arr[low..high] */` `    ``static` `int` `floorSearch(``int` `[]arr, ``int` `low,  ` `                              ``int` `high, ``int` `x) ` `    ``{ ` ` `  `        ``// If low and high cross each other ` `        ``if` `(low > high) ` `            ``return` `-1; ` `  `  `        ``// If last element is smaller than x ` `        ``if` `(x >= arr[high]) ` `            ``return` `high; ` `  `  `        ``// Find the middle point ` `        ``int` `mid = (low + high) / 2; ` `  `  `        ``// If middle point is floor. ` `        ``if` `(arr[mid] == x) ` `            ``return` `mid; ` `  `  `        ``// If x lies between mid-1 and mid ` `        ``if` `(mid > 0 && arr[mid-1] <= x && x < ` `                                    ``arr[mid]) ` `            ``return` `mid - 1; ` `  `  `        ``// If x is smaller than mid, floor ` `        ``// must be in left half. ` `        ``if` `(x < arr[mid]) ` `            ``return` `floorSearch(arr, low,  ` `                               ``mid - 1, x); ` `  `  `        ``// If mid-1 is not floor and x is ` `        ``// greater than arr[mid], ` `        ``return` `floorSearch(arr, mid + 1, high, ` `                                         ``x); ` `    ``} ` `  `  `    ``/* Driver program to check above functions */` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = {1, 2, 4, 6, 10, 12, 14}; ` `        ``int` `n = arr.Length; ` `        ``int` `x = 7; ` `        ``int` `index = floorSearch(arr, 0, n - 1,  ` `                                          ``x); ` `        ``if` `(index == -1) ` `            ``Console.Write(``"Floor of "` `+ x + ` `                     ``" dosen't exist in array "``); ` `        ``else` `            ``Console.Write(``"Floor of "` `+ x + ` `                            ``" is "` `+ arr[index]); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

Output:

```Floor of 7 is 6.
```

Time Complexity : O(Log n)