Floor in a Sorted Array in java

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);
	}
}