### CONCEPTS USED:

Searching

### DIFFICULTY LEVEL:

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:

- The idea is to use
`Binary Search`

.- Check if
`x`

is less than the first element of the array, if Yes return -1.- 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.- Else, the floor value will be present in the array.
- Take out the
`mid`

index of the array by`mid = (start + end)/2`

.- Check if value at
`mid`

matches`x`

, if Yes return its index.- Else if value at
`mid`

- Else (value at
`mid`

`> x`

) , this implies that the floor value lies at the left half.- 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.