Floor of a number

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:

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

  8. 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--;
    }  
  }
}

Previous post Generate all Pairs of 0 and 1
Next post Magical Ropes

Leave a Reply

Your email address will not be published. Required fields are marked *