Ceil and Floor in Integer Array

Ceil

Ceil of a number (say a) in an sorted array, is the number (say b_ceil in the sorted array), such that b_ceil ≥ a & b_ceil - a is minimum. It can also be said that b_ceil is the minimum number greater than or equal to a.

Floor

Similarly, Floor of a number is b_floor such that b_floor ≤ a & a - b_floor is minimum. Or, b_floor is the minimum number less than or equal to a.

Following Java program finds the ceil & floor of a number in the given array in O(log n) time

import java.util.*;
class CeilNfloor
{
 public static void main (String[] args) {
     Random random = new Random();
     int N = 15;
     int[] A = new int[N];
     for (int i=0; i<N; i++)
         A[i] = random.nextInt(100);
     Arrays.sort(A);
     System.out.println(Arrays.toString(A));
     int item = random.nextInt(100);
     System.out.println("Item is "+item);
     System.out.println("Ceil is "+ceil(A, item));
     System.out.println("Floor is "+floor(A, item));
 }
 
 static int ceil(int[] A, int item) {
     int N = A.length;
     if (item > A[N-1])  return -1;
     else                return ceil(A, 0, N-1, item);
 }
 
 static int ceil(int[] A, int low, int high, int item) {
     int mid = (low + high) >> 1;
     if (low > high)     return A[low];
     if (A[mid] == item) return A[mid];
     if (item > A[mid])  return ceil(A, mid+1, high, item);
                         return ceil(A, low, mid-1, item);
     
 }
 
 static int floor(int[] A, int item) {
     if (item < A[0]) return -1;
     return floor(A, 0, A.length-1, item);
 }
 
 static int floor(int[] A, int low, int high, int item) {
     int mid = (low + high) >> 1;
     if (low > high)     return A[high];
     if (item == A[mid]) return A[mid];
     if (item > A[mid])  return floor(A, mid+1, high, item);
                         return floor(A, low, mid-1, item);
 }
}

Output
[8, 18, 20, 24, 55, 65, 65, 66, 67, 68, 70, 74, 83, 95, 96]
Item is 4
Ceil is 8
Floor is -1