Ceiling & Floor of a number, Peak element in Mountain Array

On Day #3 of my learning journey, I delved into the fundamental concepts of Linear Search and Binary Search. I gained a profound understanding of Binary Search, recognizing its significance as one of the most fundamental and crucial concepts in computer science. Additionally, I explored various applications of Binary Search, uncovering its versatility.

I dedicated time to solving a set of questions provided in Kunal Kushwaha's DSA assignments. Specifically, for the Day 3 challenge, I focused on tackling problems related to Binary Search, enhancing my proficiency in this important algorithmic technique.

1. Finding ceiling and floor of a number

Ceiling of a number: smallest element in the array greater than or equal to the given number.

Floor of a number: largest number in the array smaller than or equal to the given number.

Example: arr = {2,3,5,9,14,16,17,18}

target = 15, so ceiling of 15 will be 16.

and, floor of 15 will be 14

Approach to Solve the Problem of Finding the Ceiling of a Number:

1. Algorithm: we can use Binary Search since the array given is a sorted array. The conventional method involves identifying the start and end positions and searching for the mid-point within the array.

2. Considering the cases:

   1. if(target > arr[mid]) : Update the start pointer to mid + 1. This indicates that the ceiling may lie to the right of the mid-point.

   2. if (target < arr[mid]): means element at arr[mid] could be a possible answer as it is greater than the target, but since we are looking for smallest number greater than or equal to the target, so we'll move left side of mid to check if there is other answer available or not.

   3. if (target == arr[mid]): Signifying that we have located the target itself, we return it directly.

   4. At the conclusion, if the condition while(start <= end) becomes false, we return start. This is because, at this point, start points to the smallest element greater than or equal to the target.

Code to find the ceiling of a number:

public class CeilingOfNumber{
        public static void main(String args[]) {
        int arr[] = {2,3,5,9,14,16,17,18};
        System.out.println(ceiling(arr, 15));
    }
}

static int ceiling(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;
        int mid = 0;

        // if the target no is greater than the largest no in array: for eg-68
        if (target > arr[arr.length - 1])
            return -1;
        while (start <= end) {
            mid = start + (end - start)/2;
            if (arr[mid] == target)
                return arr[mid];
            else if (arr[mid] < target)
                start = mid + 1;
            else if (arr[mid] > target)
                end = mid - 1;
        }
        return arr[start];
    }

Approach to solve the question of finding floor of a number:

1. Algorithm: here also, we'll use Binary Search since the array given is sorted. The conventional method involves identifying the start and end positions and searching for the mid-point within the array.

2. Considering the cases:

   1. if(target > arr[mid]) : The element at arr[mid] could potentially be a suitable answer, but we further explore to identify if there exists another number, larger but still smaller than or equal to the target. In this case, we update start as: start = mid + 1.

   2. if (target < arr[mid]): Since we are seeking the greatest number smaller than or equal to the target, we look before mid, so we update end as: end = mid-1.

   3. if (target == arr[mid]): Signifying that we have located the target itself, we return it directly.

   4. At the conclusion, if the condition while(start <= end) becomes false, we return end. This is because, at this point, end points to the greatest element smaller than or equal to the target.

Code for finding the floor of a number:

public class FloorOfNumber {
    public static void main(String[] args) {
        int arr[] = {2,3,5,9,14,16,17,18};
        System.out.println(ceiling(arr, 15));
    }

    static int floor(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;
        int mid = 0;

        // if target number is smaller than the smallest number in the array: for eg-0
        if (target < arr[0])
            return -1;

        while (start <= end) {
            mid = start + (end - start)/2;
            if (arr[mid] == target)
                return arr[mid];
            else if (arr[mid] < target)
                start = mid + 1;
            else if (arr[mid] > target)
                end = mid - 1;
        }
        return arr[end];
    }
}

2. Peak element in Mountain array

I learned about a new type of array known as a mountain array.

A mountain array starts with a series of increasing integers, reaches a peak (the highest point), and then descends with a series of decreasing integers.

For example, the array [1, 2, 3, 4, 5, 4, 3, 2, 1] is a mountain array, where the peak value '5' is at index 4.

In this problem, we aim to find the index of the peak element in the mountain array.

Here's the approach to solve the problem:

1. Algorithm: Since the elements are arranged in increasing order until the peak and then in decreasing order, binary search is a suitable approach.

2. Cases to consider:

   1. if(arr[mid] < arr[mid + 1]) : means we are ascending part of the array, hence peak element might lie after mid. In this case, we update start as: start = mid + 1.

   2. if(arr[mid] > arr[mid + 1]) : means we are in the descending part of the array, hence peak element might lie before mid, so we update end as: end = mid.

   3. At the conclusion, if the condition while(start != end) becomes false, we can either return start or end, as both will point to the peak element.

Code:

public class PeakElementMountainArray {
    public static void main(String[] args) {
        int[] arr = {1,2,3,5,6,4,3,2};
        System.out.println("Peak index: " + peakElement(arr));
    }

    static int peakElement(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = start + (end - start)/2;
            if (arr[mid] < arr[mid + 1]) {
                // ascending part of the array, peak element will lie on RHS
                start = mid + 1;
            }
            else if (arr[mid] > arr[mid + 1]) {
                // descending part of the array, this mid could be a possible answer
                // but look at LHS to find if there is another element exists
                if (arr[mid] > arr[mid - 1]) {
                    // we have found our answer
                    return mid;
                }
                else {
                    end = mid;
                }
            }
        }

        return -1;
    }
}

Here in all three questions, we are using Binary Search algorithm, hence Time Complexity of all three would be O(log n), and Space Complexity would be O(1).

Until the next update in the journey... #bytebybyte

~ Future Forward :)