# Binary Search for duplicate elements

While the binary search algorithm performs efficiently for a sorted input, there may be scenarios where we are interested in additional information about the index of the key element.

For instance, if the key is present more than once, we might be interested in knowing its first or last index. While the original algorithm will return the first index it will encounter for the key, there are some minor updates we can make to the algorithm to serve the above-mentioned use cases.

## First index of the element

Assuming the key element is present more than once, to find the first index of the key element:

2. As soon as the key element is found, note the index denoting its presence and continue the search in the input’s left half (to the key).
3. This will work as the input is given to be sorted, and the first occurrence (if any) will always be to the left of the index already found.
4. If found again, we update the index location and continue the search in the left half; Otherwise, break the loop and return the last found index.
public int firstOccurrence(int[] input, int key){
int start = 0, end = input.length - 1;
int targetIndex = -1;
while(start <= end){
int mid = start + (end - start + 1) / 2;
if(input[mid] < key){
// search space updated to second half
start = mid + 1;
} else if(input[mid] > key){
// search space updated to first half
end = mid - 1;
} else {
// key found, mark the index
// and proceed to the left of key
targetIndex = mid;
end = mid - 1;
}
}
// it will point to the left most index of key element
return targetIndex;
}


This also considers the unique key element scenario, as we have already marked the index found on its first encounter.

## Last index of the element

Similar to the first element approach, assuming the key element is present more than once, to find the last index of the key element:

2. As soon as the key element is found, note the index denoting its presence and continue the search in the input’s right half (to the key).
3. This will work as the input is given to be sorted, and the last occurrence (if any) will always be to the right of the index already found.
4. If found again, we update the index location and continue the search in the right half; Otherwise, break the loop and return the last found index.
public int firstOccurrence(int[] input, int key){
int start = 0, end = input.length - 1;
int targetIndex = -1;
while(start <= end){
int mid = start + (end - start + 1) / 2;
if(input[mid] < key){
// search space updated to second half
start = mid + 1;
} else if(input[mid] > key){
// search space updated to first half
end = mid - 1;
} else{
// key found, mark the index
// and proceed to the right of key
targetIndex = mid;
start = mid + 1;
}
}
// it will point to the right most index of key element