Binary Search

Find the floor of an element in a sorted array

Rajeev SinghAlgorithms1 mins read

Find the floor of an element in a sorted array

Problem Statement

Given a sorted array and a and a value x, find the floor of x in the array. The floor of x is the largest element in the array smaller than or equal to x. Output 1 if the floor doesn’t exist.

Example 1

Input : a[] = {1, 3, 9, 15, 15, 18, 21}, x = 5
Output : 3
3 is the largest element in the array smaller than or equal to 5.

Example 2

Input : a[] = {1, 3, 9, 15, 15, 18, 21}, x = 25
Output : 21
21 is the largest element in the array smaller than or equal to 25.

Example 3:

Input : a[] = {1, 3, 9, 15, 15, 18, 21}, x = 0
Output : -1
Since floor doesn't exist, output is -1.

Given that the array is sorted, we can apply binary search to find the floor of the element. Let’s look at the implementation:

import java.util.Scanner;

class FloorOfElementInSortedArray {
    private static int findFloorBinarySearch(int[] a, int x) {
        int n = a.length;
        int start = 0;
        int end = n-1;

        int floor = -1;

        while(start <= end) {
            int mid = (start+end)/2;

            if(x == a[mid]) {
                // a[mid] is the floor               
                return a[mid];
            } else if (x < a[mid]) {
                end = mid-1;
            } else {
                // a[mid] is the largest element found so far that is smaller than x. So it is a candidate for the floor of x
                floor = a[mid]; 
                start = mid+1;
            }
        }

        return floor;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
          a[i] = keyboard.nextInt(); 
        }
        int x = keyboard.nextInt();
        keyboard.close();

        System.out.printf("Floor(%d) = %d%n", x, findFloorBinarySearch(a, x));
    }
}
# Output
$ javac FloorOfElementInSortedArray.java
$ java FloorOfElementInSortedArray
7
1 3 9 15 15 18 21
5
Floor(5) = 3


$ java FloorOfElementInSortedArray
7
1 3 9 15 15 18 21
25
Floor(25) = 21


$ FloorOfElementInSortedArray
7
1 3 9 15 15 18 21
0
Floor(0) = -1