Last Updated: 2 Dec, 2020

Floor Value of X

Easy

Asked in companies

Solve now

Problem statement

You are given a sorted array ‘A’ and an integer ‘X’. Your task is to find and return the floor value of ‘X’ in the array.

The floor value of ‘X’ in array ‘A’ is the largest element in the array which is smaller than or equal to X.

Note: In case there is no floor value of ’X’ in the array ‘A’, return -1.

For example:

For the given arr[  ] = { 1, 2, 5, 7, 12, 14 }  and X = 10

The floor of 10 is 7 because 7 is the largest element in the array which is smaller than 10.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.

The third and the last line of each test case contains an integer representing ‘X’.

Output Format:

For each test case, print a single integer ‘K’ denoting the floor value of ‘X’ in the array. In case, there is no floor value of ’X’ in the array ‘A’, print -1.

The output of each test case will be printed on a separate line.

Note:

You do not need to input or print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5 * 10 ^ 4
0 <= X, A[i] <= 10 ^ 8

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

The idea is to iterate from left to right of the array and compare ‘X’ with the elements of the array, while it is smaller than or equal to ‘X’ then update the answer else stop.

Algorithm :

Let the function be ‘floorSearch(‘A’, ‘X’, ‘N’)’, which returns the floor of ‘X’ in the array ‘A’ of length ‘N’.

If A[0] is greater than ‘X’ return -1
Take a variable ‘ans’, that stores the floor value of ‘X’.
Run a loop from 0 to ‘N’ - 1
- If A[ i ] is less than or equal ‘X’
  - Update ‘ans’ = A[i]
- Else
  - Break
Return ‘ans’.

Solve now

02 Approach

The idea is to use binary search.

Compare the middle element of the current length array

if it is equal to ‘X’ then return ‘X’.
else if it is less than ‘X’ discard the left side of the array.
Else discard the right side of the array.

Hence in every step, we reduce the length of the search space.

Algorithm :

Let the function be ‘floorSearch(‘A’, ‘X’, ‘N’)’, which returns the floor of ‘X’ in the array ‘A’ of the length of ‘N’.

If A[0] is greater than ‘X’ then return -1
If A[N - 1] is less than or equal to ‘X’, then return A[ N - 1]
Take a variable ‘low’, initialize it to zero.
Take a variable ‘high’, initialize it to ‘N’ -1.
Take a variable ‘mid’, which stores the mid-index of the current search space.
Run a loop while ‘low’ is less than ‘high’
- Calculate ‘mid’ = ‘low’ + ( ‘high’ - ‘low’ ) / 2
- If A[mid] is equal to ‘X’ return ‘X’.
- if A[mid] is less than ‘X’
- Update ‘low’ as ‘low’ = ‘mid’ +1.
- Else ‘high’ = ‘mid’
Return A[ low -1 ]

Solve now