# Find last index of an element in a sorted array with duplicates

Given a sorted array of integers containing duplicates, write a program which returns the last index of an element.

Example:
Input:
array = {0, 1, 2, 2, 4, 5, 5, 5, 8};
num = 5;
Output:
Element 5 found at index 7

Amazon, Microsoft

## Algorithm/Insights

It is recommended to go through the binary search topic first.

We can use binary search to find the element with a slight modification.
While checking if the mid element is the desired element, ensure that mid+1 (if it exists) is greater than desired element. This will give us last index of the desired element.

## Code Snippet

```
package com.ideserve.saurabh.questions;

/**
* <b>IDeserve <br>
* Given a sorted array of integers containing duplicates, write a program which returns
* the last index of an element.
*
* @author Saurabh
*/
public class LastIndexOfElementInSortedIntegerArrayWithDuplicates {

public static int searchElementAndReturnIndex(int[] array, int num) {
if (array == null || array.length == 0) {
return -1;
}

int start = 0;
int end = array.length - 1;

while (start <= end) {
int mid = (start + end) / 2;
if ( (array[mid] == num) && ((mid == end) || (array[mid + 1] > num)) ) {
return mid;
} else if (num < array[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}

return -1;
}

public static void main(String[] args) {
int[] array = {0, 1, 2, 2, 4, 5, 5, 5, 8};
int num = 5;
int index = searchElementAndReturnIndex(array, num);
System.out.println("Element " + num + (index >= 0 ? (" found at index " + index) : " not found!"));
}
}
```

## Order of the Algorithm

Time Complexity is O(log n)
Space Complexity is O(1)