Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 2 Dec, 2020

Easy

```
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.
```

```
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’.
```

```
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.
```

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

```
1 <= T <= 5
1 <= N <= 5 * 10 ^ 4
0 <= X, A[i] <= 10 ^ 8
Time Limit: 1 sec.
```

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.

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

- If A[ i ] is less than or equal ‘X’
- Return ‘ans’.

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.

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 ]

Similar problems

Find The Single Element

Easy

Posted: 30 Oct, 2022

Find The Single Element

Easy

Posted: 30 Oct, 2022

Find minimum

Hard

Posted: 8 Nov, 2022

Search In A Sorted 2D Matrix

Moderate

Posted: 23 Nov, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Search In A Rotated Sorted Array II

Easy

Posted: 3 Feb, 2023