Find the Floor of a Number in Ascending Order Sorted Array

The floor of a number signifies, the greatest number in the array which is smaller than or equal to the target element. if the target is present then return the that else return the privious element which is smaller 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 greatest 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 7 because it is the greatest number present in the array which is smaller than the target

1, 3, 5, 7, 9 and the target is 10 then the result is 9 because it is the greatest number present in the array which is smaller than the target

3, 6, 9, 12, 15 and the target is 1 then the result is -1 because there is no greatest number present in the array which is smaller 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 a 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 Floor {
    public static int floor(int[] arr, int target) {
//        check if the target is already less than the first digit of the array
        if (target < arr[0]) {
            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[end];
    }
}

package org.wesome.dsalgo;

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

import static org.wesome.dsalgo.Floor.floor;

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

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

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

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

    @Test
    void floorTest5() {
        int[] arr = new int[]{3, 6, 9, 12, 15};
        int binarySearch = floor(arr, 1);
        Assertions.assertEquals(-1, 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)