- 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