Log inSign up
easyGeeksforGeeksNot Started

Floor in a Sorted Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Binary Search
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a sorted array arr of n integers and an integer x, find the floor of x in the array.

The floor of x is defined as the largest element in `arr` that is smaller than or equal to `x`. Return the 0-based index of the floor element. If no such element exists (i.e. all elements are greater than x), return -1.

You must implement a solution in O(log n) runtime.

Example 1 · Exact Target Present:

Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 10
Output: 3
Explanation: 10 is present at index 3 (arr[3] = 10).

Example 2 · Target Lies Between Elements:

Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 5
Output: 1
Explanation: Largest element <= 5 is 2 at index 1.

Example 3 · No Element Smaller than x:

Input: arr = [4, 6, 8, 10], x = 2
Output: -1
Explanation: All elements are > 2, so floor does not exist; return -1.

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i], x <= 106
  • arr is sorted in non-decreasing (ascending) order.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Floor condition (arr[mid] <= x) and rightward exploration.
  • Contrast Floor (largest <= x) with Ceiling (smallest >= x).
  • Implement O(log N) iterative binary search for range boundaries.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find largest value <= target in sorted array
  • Find floor of a number
  • O(log N) search on monotonic sequence

Algorithmic Decision Tree:

  • Initialize low = 0, high = n - 1, ans = -1.
  • Calculate mid = low + (high - low) / 2.
  • If arr[mid] <= x: ans = mid, low = mid + 1 (search right for larger candidate).
  • If arr[mid] > x: high = mid - 1 (search left).
  • Return ans.

Connected Patterns:

Ceiling in a Sorted ArrayLower BoundUpper BoundSearch Insert Position

1. Linear Scan from Left

Intuition

Iterate from index 0 to n - 1. If arr[i] <= x, update ans = i. If arr[i] > x, since array is sorted, break the loop early. Return ans.

When to apply: Unsorted collections or very small array sizes.

Algorithm

  1. Step 1: Initialize ans = -1.
  2. Step 2: Iterate i from 0 to arr.length - 1.
  3. Step 3: If arr[i] <= x, update ans = i.
  4. Step 4: Else (arr[i] > x), break loop.
  5. Step 5: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int findFloor(const vector<int>& arr, int x) {
7 int ans = -1;
8 for (int i = 0; i < (int)arr.size(); i++) {
9 if (arr[i] <= x) {
10 ans = i;
11 } else {
12 break;
13 }
14 }
15 return ans;
16}
17
18int main() {
19 vector<int> arr = {1, 2, 8, 10, 11, 12, 19};
20 cout << "Linear Floor of 5: " << findFloor(arr, 5) << endl;
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(N) — Worst case checks all N elements.
  • Space complexity: O(1) — Uses constant auxiliary memory.

2. Recursive Floor Binary Search

Intuition

Define solve(low, high, ans). If low > high, return ans. Calculate mid. If arr[mid] <= x, recurse on (mid + 1, high, mid) (searching right). Else recurse on (low, mid - 1, ans).

When to apply: Recursive functional approaches.

Algorithm

  1. Step 1: If low > high, return ans.
  2. Step 2: Calculate mid = low + (high - low) / 2.
  3. Step 3: If arr[mid] <= x, recurse solve(mid + 1, high, mid).
  4. Step 4: If arr[mid] > x, recurse solve(low, mid - 1, ans).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int solve(const vector<int>& arr, int low, int high, int x, int ans) {
7 if (low > high) return ans;
8 int mid = low + (high - low) / 2;
9 if (arr[mid] <= x) {
10 return solve(arr, mid + 1, high, x, mid);
11 }
12 return solve(arr, low, mid - 1, x, ans);
13}
14
15int findFloor(const vector<int>& arr, int x) {
16 return solve(arr, 0, arr.size() - 1, x, -1);
17}
18
19int main() {
20 vector<int> arr = {1, 2, 8, 10, 11, 12, 19};
21 cout << "Recursive Floor of 5: " << findFloor(arr, 5) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval at each recursive call.
  • Space complexity: O(log N) — O(log N) stack frames.

3. Iterative Binary Search Floor (Gold Standard)

Intuition

Initialize ans = -1, low = 0, high = n - 1. While low <= high: calculate mid. If arr[mid] <= x, record ans = mid and move right low = mid + 1 to find larger values <= x. Else (arr[mid] > x), move left high = mid - 1. Return ans.

When to apply: Industry standard optimal solution for finding floor element in sorted collections.

Algorithm

  1. Step 1: Initialize low = 0, high = arr.length - 1, and ans = -1.
  2. Step 2: Enter while loop with condition low <= high.
  3. Step 3: Compute mid = low + (high - low) / 2 safely.
  4. Step 4: If arr[mid] <= x: update ans = mid and search right (low = mid + 1).
  5. Step 5: Else (arr[mid] > x): search left (high = mid - 1).
  6. Step 6: Return ans.

Floor in Sorted Array Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initialize low = 0, high = 6, ans = -1
Visual state
Values and pointers at this exact step
array
S
1
2
8
10
11
12
19
0
↑ low
1
2
3
↑ mid
4
5
6
↑ high
Variables at this step
low
0
high
6
mid
3
midVal
10
ans
-1
Check / comparison
arr[mid] = 10 <= x = 5 -> FALSE (10 > 5)
Decision / next transition
10 is too large. Search left: high = mid - 1 = 2.
Why this step matters

Initialize low = 0, high = 6, ans = -1. Calculate mid = 0 + (6 - 0) / 2 = 3. arr[3] = 10.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int findFloor(const vector<int>& arr, int x) {
7 int low = 0, high = (int)arr.size() - 1;
8 int ans = -1;
9
10 while (low <= high) {
11 int mid = low + (high - low) / 2;
12
13 if (arr[mid] <= x) {
14 ans = mid; // arr[mid] is <= x, valid floor candidate
15 low = mid + 1; // Search right for larger candidates <= x
16 } else {
17 high = mid - 1; // arr[mid] is too big, search left
18 }
19 }
20 return ans;
21}
22
23int main() {
24 vector<int> arr = {1, 2, 8, 10, 11, 12, 19};
25 int x = 5;
26 cout << "Floor index of " << x << " is: " << findFloor(arr, x) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval in O(log N) iterations.
  • Space complexity: O(1) — Uses constant O(1) auxiliary pointer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear ScanO(N)O(1)Scan array from left to right tracking last arr[i] <= x.Linear scan
2.Recursive FloorO(log N)O(log N)Divide and conquer recursion.Call stack
3.Iterative Binary SearchOptimalO(log N)O(1)Halve search space, recording mid and searching right whenever arr[mid] <= x.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Searching left on arr[mid] <= x instead of right (finds smallest instead of largest <= x).

Pitfall 2:

Returning index 0 when target is smaller than all elements instead of -1.

Crucial Edge Cases to Validate:

  • Target Smaller than All Elements: arr = [4, 6, 8], x = 2 -> returns -1.
  • Target Larger than All Elements: arr = [4, 6, 8], x = 12 -> returns index 2 (last index).
  • Exact Match: arr = [2, 4, 6], x = 4 -> returns index 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the duality: Floor finds largest element <= x (searches right on match), while Ceiling finds smallest element >= x (searches left on match).
  2. Note that Floor can also be computed using upper_bound(x) - 1.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we search right (low = mid + 1) when arr[mid] <= x in Floor search?

2.What is returned if all elements in the array are strictly greater than x?

Back to DSA Sheet