Implement Lower Bound | Floor in a Sorted Array (GFG)

Given a sorted array arr[] and an integer x, find the index (0-based) of the largest element in arr[] that is less than or equal to x. This element is called the floor of x. If such an element does not exist, return -1.

Note: In case of multiple occurrences of ceil of x, return the index of the last occurrence.

Here’s the [Problem Link] to begin with.

Examples

Input: arr[] = [1, 2, 8, 10, 10, 12, 19], x = 5
Output: 1
Explanation: Largest number less than or equal to 5 is 2, whose index is 1.

Input: arr[] = [1, 2, 8, 10, 10, 12, 19], x = 11
Output: 4
Explanation: Largest Number less than or equal to 11 is 10, whose indices are 3 and 4. The index of last occurrence is 4.

Input: arr[] = [1, 2, 8, 10, 10, 12, 19], x = 0
Output: -1
Explanation: No element less than or equal to 0 is found. So, output is -1.

Constraints:

• 1 ≤ arr.size() ≤ 10⁶
• 1 ≤ arr[i] ≤ 10⁶
• 0 ≤ x ≤ arr[n-1]

Intuition & Approach

Binary search divides the search space in half repeatedly:

1. Keep a pointer lb ( lower bound) to remember the best floor index seen so far – start with -1 (meaning “no floor yet”).
2. While low ≤ high
   • Compute middle mid = (low + high) // 2.
   • Case 1:arr[mid] ≤ k
     • arr[mid] is a valid (and possibly better) floor → update lb = mid.
     • But there might be an even closer floor to the right, so move low = mid + 1.
   • Case 2:arr[mid] > k
     • Anything at mid or right is too big, so shift left with high = mid – 1.
3. Loop stops when low crosses high; lb now holds the index of the largest element ≤ k, or -1 if none exist.

This is just a small tweak of classic binary search that tracks the last “good” position seen.

Code Implementation

class Solution:
    def findFloor(self, arr, k):
        n = len(arr)
        lb = -1               # floor index; -1 means no floor yet
        low, high = 0, n - 1  # binary-search boundaries

        while low <= high:
            mid = (low + high) // 2        # middle index

            if arr[mid] <= k:
                lb = mid                   # potential (better) floor
                low = mid + 1              # look on the right side
            else:
                high = mid - 1             # look on the left side

        return lb                           # final floor index (or -1)

Code Explanation

• lb (lower bound) keeps the best floor found so far.
• Binary search window [low … high] always contains candidates we haven’t ruled out.
• When arr[mid] is ≤ k, it’s a valid floor, so store its index and push low right to hunt for an even closer floor.
• When arr[mid] is > k, everything right of mid is larger than k; discard that half by moving high left.
• The loop ends when no unexamined indices remain. The answer is whatever index lb holds (or -1).

Dry Run (arr = [1, 2, 8, 10, 11], k = 9)

Output index 2 (value 8), which is the largest number ≤ 9.

Time & Space Complexity

Binary search guarantees logarithmic time, and only a couple of integer variables are used, so space stays constant.

Conclusion

Finding the floor in a sorted array is a classic example of how small tweaks to binary search can solve seemingly new problems:

• Track the best candidate while you divide the search space.
• Update the candidate whenever you find a closer match.

Master this pattern and you’ll be equipped for a wide range of “closest element” questions on sorted data. Happy searching!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.