Find Nearest Greater and Smaller Element

Problem Statement

In find the nearest greater and smaller element problem, we have given an unsorted array, you have to find two numbers from an array that are just smaller than a number X and just greater than a number X.

The Floor denotes the nearest smaller element and Ceil denotes the nearest greater element.

Input Format

First-line containing two integer values N and X.

Second-line containing an array of size N.

Output Format

Print two integers in two lines where the first integer denotes the nearest greater element and the second integer denotes the nearest smaller element. If there is no number greater than X then print “No floor of x found” in the position of the first integer. If there is no number smaller than X then print “No ceil of x found” in the position of the second integer.

Constraints

• 1<=N<=100000
• -1e9<=X<=1e9
• -1e9<=a[i]<=1e9 where a[i] denotes the element of the given array.

Algorithm for Find Nearest Greater and Smaller Element

1. Initialize two variables just_greater and just_smaller with some very large and small value respectively.

2. Loop through the array as:

• If the array element is greater than x but smaller than just_greater then just_greater = arr[i]

• If the array element is smaller than x but larger than just_smaller then just_smaller = arr[i]

3. Print just greater element if exist for x else print “No floor of x found” and print just smaller element if exist for x else print “No ceil of x found”.

Note: It is simply the modification of finding the second minimum and maximum in an array with a variation of having a reference number with respect to which it is found.

Implementation

C++ Program for Find Nearest Greater and Smaller Element

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,x;
  cin>>n>>x;
  long long int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  int just_greater=INT_MAX,just_smaller=INT_MIN;
  for(int i=0; i<n; i++)
  {
    //if element is greater than x but smaller than present just_greater
    if(arr[i] > x and arr[i] < just_greater)
      just_greater = arr[i];
      
    //if element is Smaller than x but smaller than present just_smaller
    if(arr[i] < x and just_smaller < arr[i])
      just_smaller = arr[i];
  }   
  if(just_smaller !=INT_MIN)
    cout<<just_smaller<<endl;
  else
    cout<<"No floor of x found\n";
  if(just_greater != INT_MAX)
    cout<<just_greater<<endl;
  else
    cout<<"No Ceil of x found\n";
  return 0;
}

import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int arr[] = new int[n-1];
        for(int i=0;i<n-1;i++)
        {
            arr[i] = sr.nextInt();
        }
        int just_greater=10000000,just_smaller=-10000000;
        for(int i=0; i<n; i++)
        {
          //if element is greater than x but smaller than present just_greater
          if(arr[i] > x && arr[i] < just_greater)
            just_greater = arr[i];
          //if element is Smaller than x but smaller than present just_smaller
          if(arr[i] < x && just_smaller < arr[i])
            just_smaller = arr[i];
        }   
        if(just_smaller != -10000000)
          System.out.println(just_smaller);
        else
          System.out.println("No floor of x found");
        if(just_greater != 10000000)
          System.out.println(just_greater);
        else
          System.out.println("No Ceil of x found");
    }
}

8 0
-3 -4 10 0 3 -2 15 3

-2
3