Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Floor of a number

Last Updated on March 23, 2022 by Ria Pathak

Searching

Easy

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a sorted array `A` and a number `x`. find the largest value in the array that is less than or equal to `x` and print its index.

See original problem statement here

#### For Example:

``````Input :  N = 7, x = 5
A[] = [1, 2, 8, 10, 11, 12, 19]

Output : 1 (as 2 <= 5 and it is present on index 1)``````

Can we use `Binary Search` here ?

Given that the array is sorted, `Binary Search` would be an efficient alternative to quickly search for the element that is less than or equal to `x` in `Logarithmic Time Complexity`.

#### SOLVING APPROACH:

1. The idea is to use `Binary Search`.
2. Check if `x` is less than the first element of the array, if Yes return -1.
3. Check if `x` is greater than the last element of the array, if Yes return the `index` of the last element as it is going to be its floor value.
4. Else, the floor value will be present in the array.
5. Take out the `mid` index of the array by `mid = (start + end)/2`.
6. Check if value at `mid` matches `x`, if Yes return its index.
7. Else if value at `mid`
8. Else (value at `mid` `> x`) , this implies that the floor value lies at the left half.
9. Recursively go on searching for the floor value, if `step` `5` becomes true, return index. Else return the `end` value.

### ALGORITHM:

``````if (x is less than first element of the array)
print -1
else if (x is greater than last element of the array)
print last element index
else
Search in array

Search in array
mid = (first + last)/2
if (element at mid index = x)
print mid
else if (element at mid index < x)
Search in right half of the array with first = mid + 1
else
Search in left half of the array with last = mid - 1
print last``````

### ILLUSTRATION:

``````A[] = [1, 2, 8, 10, 11, 12, 19]
x = 5

i = 0
j = 6
mid = (0 + 6) / 2 = 3
Since A[3] > x
j = mid - 1 = 2

i = 0
j = 2
mid = (0 + 2) / 2 = 1
Since A[1] < x
i = mid + 1 = 1 + 1 = 2

i = 2
j = 2
mid = (2 + 2) / 2 = 2
Since A[2] > x
j = mid - 1 = 2 - 1 = 1

Since, i > j, we will stop here and print index j i.e. 1
as A[1] i.e. 2 is less than or equal to x.``````

### SOLUTIONS:

```
#include <stdio.h>

int floor_number(int arr[], int low, int high, int x){
if(low <= high){
int mid = (low + high)/2;

//If x matches a element in the array, return its index
if(arr[mid] == x)
return mid;

//if x > mid value of array, search in the right half
else if(arr[mid] < x)
return floor_number(arr, mid+1, high, x);

//if x < mid value of array, search in the left half
else
return floor_number(arr, low, mid-1, x);
}
//If no value matches x , return high
return high;
}
int main()
{
int t; scanf("%d",&t);
while(t--){
int n, x; scanf("%d %d", &n, &x);
int arr[n];
int low = 0, high = n-1;

for(int i=0; i<n; i++)
scanf("%d", &arr[i]);

//If x is smaller than the first element print -1
if(x < arr[0])
printf("-1\n");

/* If x is greater than the last element,
its floor value will be the last element */
else if(x > arr[n-1])
printf("%d\n",n-1);
else
//Floor value is present in the array, check for it
printf("%d\n", floor_number(arr, low, high, x));
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

int floor_number(int arr[], int low, int high, int x){
if(low <= high){
int mid = (low + high)/2;

//If x matches a element in the array, return its index
if(arr[mid] == x)
return mid;

//if x > mid value of array, search in the right half
else if(arr[mid] < x)
return floor_number(arr, mid+1, high, x);

//if x < mid value of array, search in the left half
else
return floor_number(arr, low, mid-1, x);
}
//If no value matches x , return high
return high;
}
int main()
{
int t; cin>>t;
while(t--){
int n, x; cin>>n>>x;
int arr[n];
int low = 0, high = n-1;

for(int i=0; i<n; i++)
cin>>arr[i];

//If x is smaller than the first element print -1
if(x < arr[0])
cout<<-1<<endl;

/* If x is greater than the last element,
its floor value will be the last element */
else if(x > arr[n-1])
cout<<n-1<<endl;
else
//Floor value is present in the array, check for it
cout<<floor_number(arr, low, high, x)<<endl;
}
return 0;
}
```
```
import java.util.*;
import java.io.*;

public class Main {
static int floor_number(int arr[], int low, int high, int x){
if(low <= high){
int mid = (low + high)/2;

//If x matches a element in the array, return its index
if(arr[mid] == x)
return mid;

//if x > mid value of array, search in the right half
else if(arr[mid] < x)
return floor_number(arr, mid+1, high, x);

//if x < mid value of array, search in the left half
else
return floor_number(arr, low, mid-1, x);
}
//If no value matches x , return high
return high;
}
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0){
int n = sc.nextInt();
int x = sc.nextInt();
int arr[] = new int[n];
int low = 0, high = n-1;

for(int i=0; i<n; i++)
arr[i] = sc.nextInt();

//If x is smaller than the first element print -1
if(x < arr[0])
System.out.println("-1");

/* If x is greater than the last element,
its floor value will be the last element */
else if(x > arr[n-1])
System.out.println(n-1);
else
//Floor value is present in the array, check for it
System.out.println(floor_number(arr, low, high, x));
t--;
}
}
}
```

[forminator_quiz id="1108"]

This article tried to discuss Searching. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.