Given a sorted array arr[] of size N without duplicates, and given a value x. Find the floor of x in given array. Floor of x is defined as the largest element K in arr[] such that K is smaller than or equal to x.

Try to use binary search to solve this problem.

#### Input

- First line of input contains number of integers in array, N and element whose floor is to be searched.
- Last line of input contains array elements.

#### Constraints

- 1 ≤ N ≤ 10^5
- 1 ≤ arr[i] < 10^9
- 0 ≤ X ≤ arr[n-1]

#### Output

Output the index of floor of x if exists, else print -1. Use 0-indexing.

#### Example

**Sample Input**

7 0 1 2 8 10 11 12 19

**Sample Output**

-1

**Sample Input**

7 5 1 2 8 10 11 12 19

**Sample Output**

1

**Sample Input**

7 10 1 2 8 10 11 12 19

**Sample Output**

3

**Explanation**

Testcase 1: No element less than or equal to 0 is found. So output is "-1". Testcase 2: Number less than or equal to 5 is 2, whose index is 1(0-based indexing). Testcase 3: Number less than or equal to 10 is 10 and its index is 3.

## Solution of Floor in a Sorted Array in java:–

import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main (String[] args) throws java.lang.Exception { //your code here Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int arr[] = new int[n]; for(int i=0;i<n;i++) { arr[i]=sc.nextInt(); } int l=0; int r=n-1; int mid=0; int ans=-1; while(l<=r) { mid=(l+r)/2; if(arr[mid]==k) { ans=mid; break; } else if(arr[mid]>k) { r=mid-1; } else{ ans=mid; l=mid+1; } } System.out.print(ans); } }

## Add a Comment