1. Introduction

Searching for a specific element in an array is a basic operation. In a sorted array, the elements are arranged in either ascending or descending order. When multiple occurrences of an element exist, it might be useful to find the first or last occurrence of the element. Using a modified version of binary search, we can achieve this efficiently.

2. Program Steps

1. Start with the entire array as the search space.

2. Calculate the mid-point of the search space.

3. If the mid-point element matches the target, check its left (for first occurrence) or right (for last occurrence) to ensure it’s the desired occurrence.

4. If the mid-point element is greater than the target, adjust the search space to the left half.

5. If the mid-point element is less than the target, adjust the search space to the right half.

6. Continue until the search space is exhausted or the desired occurrence is found.

3. Code Program

public class FirstLastOccurrence {

    public static int findFirst(int[] arr, int x) {
        int low = 0, high = arr.length - 1, result = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == x) {
                result = mid;
                high = mid - 1;  // Move to the left part
            } else if (arr[mid] < x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }

    public static int findLast(int[] arr, int x) {
        int low = 0, high = arr.length - 1, result = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == x) {
                result = mid;
                low = mid + 1;  // Move to the right part
            } else if (arr[mid] < x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 3, 4, 5};
        int x = 2;
        System.out.println("First occurrence of " + x + " is at index: " + findFirst(arr, x));
        System.out.println("Last occurrence of " + x + " is at index: " + findLast(arr, x));
    }
}
x

Output:

First occurrence of 2 is at index: 1
Last occurrence of 2 is at index: 3

4. Step By Step Explanation

1. We have two functions findFirst and findLast that implement the modified binary search.

2. When we find an occurrence in the findFirst function, we update the result and move our search space to the left half by adjusting the high pointer. This ensures we find the first occurrence.

3. Similarly, in the findLast function, we move the search space to the right half by adjusting the low pointer to find the last occurrence.

4. If the element is not found, -1 is returned to indicate the absence of the element.

5. In the main function, we've given an example with the number 2 in a sorted array. The functions correctly identify the first and last positions of the number.