Last Updated on March 23, 2022 by Ria Pathak
CONCEPTS USED:
Searching
DIFFICULTY LEVEL:
Easy
PROBLEM STATEMENT(SIMPLIFIED):
Given a sorted array
Aand a numberx. find the largest value in the array that is less than or equal toxand 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 Searchwould be an efficient alternative to quickly search for the element that is less than or equal toxinLogarithmic Time Complexity.
SOLVING APPROACH:
- The idea is to use
Binary Search.- Check if
xis less than the first element of the array, if Yes return -1.- Check if
xis greater than the last element of the array, if Yes return theindexof 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
midindex of the array bymid = (start + end)/2.- Check if value at
midmatchesx, 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
step5becomes true, return index. Else return theendvalue.
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 lastILLUSTRATION:
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.