Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Two binary searches: one for the last element ≤ x, one for the first element ≥ x.
  2. 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