Problem

Given a sorted array and a value x, find the floor of the key in an array. floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order.

Definition

floor is the greatest element smaller than or equal to x

Examples

Example 1:

1
2
3

 Input: arr = [1, 2, 4, 6, 10, 12, 14], x = 5
 Output: 4
 Explanation: The largest element less than or equal to 5 is 4

Example 2:

1
2
3

 Input: arr = [1, 2, 4, 6, 10, 12, 14], x = 11
 Output: Floor = 10, Ceiling = 12
 Explanation: The largest element less than or equal to 11 is 10

Example 3:

1
2
3

 Input: arr = [1, 2, 4, 6, 10, 12, 14], x = 15
 Output: Floor = 14, Ceiling = -1
 Explanation: The largest element less than or equal to 15 is 14

Solution

Method 1 - Binary Search

O(lgn) solution using modified Binary Search Here are the steps:

  • Initialize start to 0 and end to the length of the array minus one.
  • Use a while loop with the condition start <= end to continue binary search.
  • Calculate the middle index mid.
  • If arr[mid] equals x, return arr[mid].
  • If arr[mid] is less than x, update floor to arr[mid] and move the start pointer to mid + 1.
  • If arr[mid] is greater than x, move the end pointer to mid - 1.
  • Continue until the while loop exits and return the floor.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public static int findFloor(int[] arr, int x) {
        int start = 0, end = arr.length - 1;
        int floor = -1;

        while (start <= end) {
            int mid = (start + end) / 2;
            // a[mid] is the floor
            if (arr[mid] == x) {
                return arr[mid];
            } else if (arr[mid] < x) {
	            // 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 = arr[mid];
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return floor;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def find_floor(arr, x):
    start, end = 0, len(arr) - 1
    floor = -1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == x:
            return arr[mid]
        elif arr[mid] < x:
            floor = arr[mid]
            start = mid + 1
        else:
            end = mid - 1

Complexity

  • ⏰ Time complexity: O(log n), due to binary search.
  • 🧺 Space complexity: O(1), as no extra space is used apart from a few variables.