Problem Statement

Platform: GeeksforGeeks

You are given a sorted array arr[] and an integer x. Your task is to find the index of the largest element in the array that is less than or equal to x.

1. Return -1 if no such element exists.
2. If multiple elements equal the floor, return the last occurrence.

Example:

✅ The largest element ≤ 11 is 10. The last occurrence is at index 4.

👉 Try this problem here: GeeksforGeeks – Floor in a Sorted Array

Intuition: What is “Floor” and Why It Matters

Imagine climbing stairs:

1. You want to step as high as possible without going past a certain height.
2. That step is your floor – the largest number ≤ x.

In arrays:

1. The floor of x is the largest number smaller than or equal to x.
2. Because the array is sorted, we can search efficiently with binary search instead of checking every element.

This is faster and helps you handle large arrays with millions of elements.

Multiple Approaches

1️⃣ Linear Search (Easy but Slow)

Check each element from left to right. If it’s ≤ x, update the answer.

1. Time Complexity: O(n) – slow for large arrays
2. Space Complexity: O(1) – constant memory

2️⃣ Binary Search (Fast & Efficient)

Binary search cuts the search space in half at every step.

1. Time Complexity: O(log n) – very fast
2. Space Complexity: O(1) – no extra space

Dry Run / Step-by-Step

Input: arr = [1, 2, 8, 10, 10, 12, 19], x = 11

✅ Finds floor = 10 at index 4.

Code Explanation in Simple Words

1. ans = -1 → stores best candidate for floor.
2. Use low and high as binary search boundaries.
3. mid = low + (high - low)/2 → safe midpoint.
4. If arr[mid] <= x, it can be the floor → move right to find last occurrence.
5. If arr[mid] > x, move left → floor is smaller.
6. Loop ends when low > high, return ans.

Edge Cases to Remember

1. x < arr[0] → return -1 (floor doesn’t exist)
2. x ≥ arr[n-1] → return last index (floor is last element)
3. Duplicates → always return last occurrence

Story-Based Visual Example: “Alice’s Book Shelf Adventure” 📚

Scenario:

1. Alice is a librarian.
2. Books are arranged by height on a shelf.
3. She has a new book and wants to place it next to the tallest book shorter than or equal to hers.
4. Instead of checking each book, she uses a binary search approach to find the position quickly.

"Alice is scanning the bookshelf, which represents a sorted array: [1, 2, 8, 10, 10, 12, 19]. She is thinking where to place her new book labeled 11. This step represents the initial step of the floor algorithm, understanding the array elements."

"Alice places the book labeled 11 right after the last 10 on the shelf. This demonstrates finding the floor: the largest number ≤ 11 is 10, and the book is positioned next to it, illustrating the last occurrence logic."

"From a top view, Alice is scanning all the books. This shows how binary search would conceptually divide the array: she quickly decides which section the book 11 belongs to without checking every book, demonstrating efficient search."

"Alice has successfully placed the book 11 at the correct position. The floor of 11 is 10 (index 4). This visual confirms the algorithm’s result: the new element is positioned immediately after the last element ≤ x, exactly as binary search would determine."

Why This Problem is Important

1. Strengthens binary search skills
2. Teaches last occurrence / boundary conditions handling
3. Makes you think algorithmically, not just about numbers
4. Story-based learning improves retention and understanding

Conclusion

1. Linear search: easy but slow (O(n))
2. Binary search: fast, elegant (O(log n))
3. Multiple dry run steps make it easy to follow
4. Story-based images make abstract concepts concrete and memorable