Array Questions (Binary Search Problems) Part-4

Problem-22 find the nearestLowest and nearest greater value in the given sorted array

Approach is doing with Binary Search , like we are looking for 72 so the nearest lowest will come 60 and nearest greater will come 80. First it get the middle element if middle element > search element so make high as mid -1 other wise low  as mid + 1, and also keeping the arr[mid] for lowest and greater.

public class LowestAndGreatest {
    public static void main(String[] args) {
        int arr[] = { 10, 12, 15, 17, 19, 20, 25, 27, 30, 35, 40 };
        int search = 29;
        int nearestLowest = 0;
        int nearestGreater = 0;
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        for (int i = 0; i < arr.length; i++) {
            mid = (low + high) / 2;

            if (search > arr[mid]) {
                low = mid + 1; // Left to right
                nearestLowest = arr[mid];

            } else if (search < arr[mid]) {
                high = mid - 1; // right to left
                nearestGreater = arr[mid];
            } else {
                nearestLowest = nearestGreater = arr[mid];
                break;
            }
        }
        System.out.println("Lowest " + nearestLowest + " Greater " + nearestGreater);
    }
}

TC O(Log N) and SC O(1)

Problem-23 Find the First and Last Occurance in Sorted Array

Approach is First Looking for the first Index occurrence so do Binary Search only thing is if element found so don't break for the loop assuming this would be the firstIndex element and keep squeezing the high so high = mid-1. The similar process goes fro the last Index the only thing is keep squeezing the low so low = mid+1.

public class FindTheFirstAndLastOccurance {
    public static void main(String[] args) {
        int arr[] = { 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4 };
        int searchElement = 2;
        int firstIndex = -1;
        int lastIndex = -1;
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (searchElement > arr[mid]) {
                low = mid + 1;
            } else if (searchElement < arr[mid]) {
                high = mid - 1;
            } else if (searchElement == arr[mid]) {
                firstIndex = mid;
                high = mid - 1;
            }
        }
        lastIndex = -1;
        low = 0;
        high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (searchElement > arr[mid]) {
                low = mid + 1;
            } else if (searchElement < arr[mid]) {
                high = mid - 1;
            } else if (searchElement == arr[mid]) {
                lastIndex = mid;
                low = mid + 1;
            }
        }
        System.out.println("First Index " + firstIndex);
        System.out.println("Last Index " + lastIndex);
    }
}

Problem-24 Find the Frequency of the Element in the Sorted Array

Same logic as above problem only thing is do lastIndex - firstIndex.

public class FindTheOccuranceOfAnElement24 {
    public static void main(String[] args) {
        int arr[] = { 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4 };
        int searchElement = 2;
        int firstIndex = -1;
        int lastIndex = -1;
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (searchElement > arr[mid]) {
                low = mid + 1;
            } else if (searchElement < arr[mid]) {
                high = mid - 1;
            } else if (searchElement == arr[mid]) {
                firstIndex = mid;
                high = mid - 1;
            }
        }
        lastIndex = -1;
        low = 0;
        high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (searchElement > arr[mid]) {
                low = mid + 1;
            } else if (searchElement < arr[mid]) {
                high = mid - 1;
            } else if (searchElement == arr[mid]) {
                lastIndex = mid;
                low = mid + 1;
            }
        }
        System.out.println("Frequency is " + ((lastIndex - firstIndex) + 1));

    }
}

That's All folks catch you in next Tutorial 😀