#### Ceil

Ceil of a number (say a) in an sorted array, is the number (say b_{ceil}in the sorted array), such that

**b**. It can also be said that b

_{ceil}≥ a & b_{ceil}- a is minimum_{ceil}is the minimum number greater than or equal to a.

#### Floor

Similarly, Floor of a number is b_{floor}such that

**b**. Or, b

_{floor}≤ a & a - b_{floor}is minimum_{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); } }

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

## No comments:

## Post a Comment