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.

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

- Start with the normal binary search algorithm.
- 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).
- 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.
- 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
// or -1 if not found
return targetIndex;
}
```

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

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

- Start with the normal binary search algorithm.
- 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).
- 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.
- 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
// or -1 if not found
return targetIndex;
}
```

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

Be notified of new posts. Subscribe to the RSS feed.