Find the Ceiling of a Number in Ascending Order Sorted Array

The ceiling of a number signifies, the smallest number in the array which is greater than or equal to the target element. if the target is present then return the that else return the next element which is greater than the target and is present in the array.

for example, the array is

1,3,5,7,9 and the target is 5 then the result is 5 because it is the smallest number present in the array which is equal to the target element

1,3,5,7,9 and the target is 8 then the result is 9 because it is the smallest number present in the array which is greater than the target

1,3,5,7,9 and the target is 10 then the result is -1 because no element in the array which is greater than or equal to the target element

3, 6, 9, 12, 15 and the target is 1 then the result is 3 because it is the smallest number present in the array which is greater than the target

If need to find a target element in a sorted array, find the pattern and think of a Binary Search first.

the main concept of binary search is that the target element lies between the start and end index.

the algorithm will have 2 cases, let's understand
case 1: the target element is found
case 2: if the target element is not found and the start becomes greater than the end ie start = end+1, the condition for the while loop will violate, the exit case will execute, and the start element will be the smallest number greater than the target.

It is exactly binary search, if the element is found the binary search will return it else then instead of returning -1, return the start

package org.wesome.dsalgo;

public class Ceiling {
    public static int ceiling(int[] arr, int target) {
//        check if the target is already greater than the last digit of the array, so it will be the ceiling of the array
        if (target > arr[arr.length - 1]) {
            return -1;
        }

        int start = 0, end = arr.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            // If the target element is present in the middle itself
            if (arr[mid] == target) {
                return arr[mid];
            }
            // In ascending order sorted array, If the target is smaller than mid-element, then it can only be present in left sub-array
            else if (arr[mid] > target) {
                end = mid - 1;
            }
            // Else the element can only be present in right sub-array
            else {
                start = mid + 1;
            }
        }
        return arr[start];
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import static org.wesome.dsalgo.Ceiling.ceiling;

public class BinarySearchTest {
    @Test
    void ceilingTest1() {
        int[] arr = new int[]{1, 2, 3, 4, 5};
        int binarySearch = ceiling(arr, 3);
        Assertions.assertEquals(3, binarySearch);
    }

    @Test
    void ceilingTest2() {
        int[] arr = new int[]{2, 4, 6, 8, 10};
        int binarySearch = ceiling(arr, 11);
        Assertions.assertEquals(-1, binarySearch);
    }

    @Test
    void ceilingTest3() {
        int[] arr = new int[]{1, 3, 5, 7, 9};
        int binarySearch = ceiling(arr, 4);
        Assertions.assertEquals(5, binarySearch);
    }

    @Test
    void ceilingTest4() {
        int[] arr = new int[]{2, 3, 5, 9, 14, 16, 18};
        int binarySearch = ceiling(arr, 15);
        Assertions.assertEquals(16, binarySearch);
    }

    @Test
    void ceilingTest5() {
        int[] arr = new int[]{3, 6, 9, 12, 15};
        int binarySearch = ceiling(arr, 1);
        Assertions.assertEquals(3, binarySearch);
    }
}

plugins {
    id 'java'
    id "io.freefair.lombok" version "6.4.1"
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}

The algorithm has time complexity of O(log N) and space complexity of O(log N)