Create Ceiling.java

BiswaSubudhi · web-flow · commit 927d36bb8770 · 2022-10-19T07:59:02.000+05:30
This java program returns the ceiling of a given number in a sorted array
diff --git a/Ceiling.java b/Ceiling.java
@@ -0,0 +1,36 @@
+public class Ceiling {
+
+    public static void main(String[] args) {
+        int[] arr = {2, 3, 5, 9, 14, 16, 18};
+        int target = 15;
+        int ans = ceiling(arr, target);
+        System.out.println(ans);
+    }
+
+    // return the index of smallest no >= target
+    static int ceiling(int[] arr, int target) {
+
+        // but what if the target is greater than the greatest number in the array
+        if (target > arr[arr.length - 1]) {
+            return -1;
+        }
+        int start = 0;
+        int end = arr.length - 1;
+
+        while(start <= end) {
+            // find the middle element
+//            int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java
+            int mid = start + (end - start) / 2;
+
+            if (target < arr[mid]) {
+                end = mid - 1;
+            } else if (target > arr[mid]) {
+                start = mid + 1;
+            } else {
+                // ans found
+                return mid;
+            }
+        }
+        return start;
+    }
+}
