Practice › Binary Search
Floor and Ceil in a Sorted Array
Easy · Binary Search · Asked at Amazon, Microsoft, TCS, Infosys, Wipro
The array is sorted. Print the floor of x (largest element ≤ x) and the ceil of x (smallest element ≥ x). Print -1 for a value that does not exist.
Input
First line: n x. Second line: the sorted array.
Output
Two integers: floor and ceil.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i], x ≤ 10^9
Example 1
Input
6 5 3 4 4 7 8 10
Output
4 7
Example 2
Input
6 8 3 4 4 7 8 10
Output
8 8
Hints
- Two binary searches: one for the last element ≤ x, one for the first element ≥ x.
- While searching, remember the best candidate seen so far (start at −1).
Approach
Floor: binary search; whenever a[mid] ≤ x, record a[mid] as a candidate and search right, otherwise search left. Ceil is the mirror image: when a[mid] ≥ x, record and search left. If no candidate was recorded, the answer stays −1.
Complexity: O(log n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long x;
cin >> n >> x;
vector<long long> a(n);
for (auto &v : a) cin >> v;
long long fl = -1, ce = -1;
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] <= x) fl = a[mid], lo = mid + 1;
else hi = mid - 1;
}
lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] >= x) ce = a[mid], hi = mid - 1;
else lo = mid + 1;
}
cout << fl << " " << ce << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, x, a = data[0], data[1], data[2:]
fl = ce = -1
lo, hi = 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] <= x:
fl, lo = a[mid], mid + 1
else:
hi = mid - 1
lo, hi = 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] >= x:
ce, hi = a[mid], mid - 1
else:
lo = mid + 1
print(fl, ce)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long x = sc.nextLong();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long fl = -1, ce = -1;
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] <= x) { fl = a[mid]; lo = mid + 1; }
else hi = mid - 1;
}
lo = 0;
hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] >= x) { ce = a[mid]; hi = mid - 1; }
else lo = mid + 1;
}
System.out.println(fl + " " + ce);
}
}Solve Floor and Ceil in a Sorted Array online · All practice problems