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:

1. Start with the normal binary search algorithm.
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
    // 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.

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:

1. Start with the normal binary search algorithm.
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
    // 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.