# 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.