C Program to Find Floor of a Number in Sorted Array

  • Write a program to find floor of a number in a sorted array.
  • Algorithm to find the largest number smaller than or equal to X in a sorted integer array.

Given a sorted integer array and an integer X. We have to find the largest number smaller than or equal to X in input array.

Sorted array : [1 3 5 6 8 10 11 14 15 20].
  • Floor : Floor of a number X is the largest number smaller than or equal to X in sorted array. If X is present in array then X is the floor otherwise largest number smaller than X.
    • Floor of 12 is 11
    • Ceiling of 15 is 15

Let inputArray be the given sorted array of size N.
Linear search : O(n)
Algorithm to find floor of a number using linear search
  • If X is smaller than smallest element of inputArray(inputArray[0]) then no ceiling element exist for X.
  • If X is larger than largest element of inputArray(inputArray[N-1]), then largest element of inputArray(inputArray[N-1]) is floor of X.
  • Traverse inputArray from index 0 to N-1 and find an index i where inputArray[i] =< X && inputArray[i+1] > X.
  • Return inputArray[i] as it is the largest element smaller than or equal to X.

C program to find floor of a number in sorted array using linear search.

#include <stdio.h>

/* This function prints the Floor of K in sorted array */
void printFloorElement(int *array, int size, int K){
    int i;
 
    /* If K is smaller that smallest element of array, 
    then No floor element of K exist in array */
    if(K <= array[0])
       printf("No Floor Element");
 
    /* If K is larger than the largest element of array, 
    then largest element of array is floor of K */
    if(K > array[size-1])
       printf("%d", array[size-1]);
 
    /* Traverse input array and search for appropriate 
    position of K in sorted array */
    for(i = 0; i< size; i++){
        if(K == array[i])
            printf("%d", array[i]);
     
        if(array[i] < K && array[i+1] > K)
            printf("%d", array[i]);
    }  
}

int main(){
    int array[10] = {1, 2, 5, 5, 8, 10, 11, 14, 15, 16};

    printFloorElement(array, 10, 12);

    return 0;
}
Output
11
By using customized binary search : O(LogN)
Algorithm to find largest number smaller than given number X.
  • If X is smaller than smallest element of inputArray(inputArray[0]) then no ceiling element exist for X.
  • If X is larger than largest element of inputArray(inputArray[N-1]), then largest element of inputArray(inputArray[N-1]) is floor of X.
  • Now do customized binary search.
    • If X is larger than array[mid], then check if K <= array[mid+1] or recursively search in right sub array.
    • If X is smaller than array[mid], then check if array[mid-1] < X or recursively search in left sub array

C program to find floor of a number in sorted array

#include <stdio.h>

/* This function returns the index of floor of K in sorted array */
int getFloorIndex(int *array, int left, int right, int K) {
  int mid;    
 
  /* If K is smaller that smallest element of array, 
   then No floor element of K exist in array */
   if(K <= array[left])
      return -1;  
 
   /* If K is larger than the largest element of array, 
   then largest element of array is floor of K */
   if(K > array[right])
       return right;  
 
  mid = (left + right)/2;
  /* CUSTUMIZED BINARY SEARCH */
  /* If K is equal to middle element, then return mid */
  if(array[mid] == K)
    return mid;
     
  /* If K is larger than array[mid], then check if 
  array[mid+1] is > K or recursively search in right 
  sub array */ 
  else if(K > array[mid]){
    if(mid + 1 <= right && K <= array[mid+1])
      return mid;
    else
      return getFloorIndex(array, mid+1, right, K);
  }
  /* If K is smaller than array[mid], then check if 
  array[mid-1] is < K or recursively search in left 
  sub array */    
  else {
    if(mid - 1 >= left &&  array[mid-1] < K)
      return mid-1;
    else    
      return getFloorIndex(array, left, mid - 1, K);
  }
}

int main(){
    int array[10] = {-1, 0, 3, 5, 6, 8, 10, 15, 16, 19};
    int index = getFloorIndex(array, 0, 9, 12);
    if(index == -1){
        printf("No Ceiling Element found in Array");
    } else {
 printf("Floor Element : %d", array[index]);
    }
    return 0;
}
Output
Floor Element : 10
Posted by
Labels: ,