Index of Last Occurrence in Sorted Array

Problem: Given a sorted array wutg repetition and an element x, we need to find index of last occurrence of x.

Examples:

Input: arr[] = {10, 15, 20, 20, 40, 40}, x = 20
Output: 3

Input: arr[] = {5, 8, 8, 10, 10}, x = 10
Output: 4

Input arr[] = {8, 10, 10, 12}, x = 7
Output: -1

Naive solution is to traverse the array from right side which has a time complexity of O(n), but we could make use of Iterative or Recursive Binary Search. The problem gets tricky when the element we want to find also exists after we found with mid index.

So, we need to make some changes in our binary search implementation, if there is a match for mid index:

• check if mid == arr.length - 1 or check if next index element is not equal to current mid index element (arr[mid + 1] != arr[mid]), if either of the case matches return mid
• else, check in the right half of the array (repeat).

Solution:

package com.raindroplabs.searching;

/**
 * <p><b>Last Occurrence:</b> is to find index of last occurrence of a given
 * element in an array or list. This algorithm uses Binary Search.</p>
 * <p><b>Time Complexity:</b> O(log n)</p>
 * <p><b>Usage:</b></p>
 * {@code
 * int[] lastOccNums = {5, 10, 10, 10, 10, 20, 20};
 * LastOccurrence.of(lastOccNums, 10);
 * LastOccurrence.of(lastOccNums, 0, lastOccNums.length, 10)
 * }
 */
public class LastOccurrence {

    /**
     * <b>Flow:</b>
     * <p><b>Iterative Implementation</b></p>
     * <p>We used iterative binary search, the problem gets tricky when the element
     * we want to find also exists after we found with mid index.
     * So, we need to make some changes in our binary search implementation,
     * if there is a match for mid index:</p>
     * <p>
     *     <ul>
     *         <li>
     *             check if mid == arr.length - 1 or check if next mid index element is not equal
     *             to current mid index element (arr[mid + 1] != arr[mid]), if either of the
     *             case matches return mid
     *         </li>
     *         <li>
     *             else, check in the right half of the array (repeat).
     *         </li>
     *     </ul>
     * </p>
     * @param arr integer array
     * @param x element to search
     * @return index of the given element or -1 if not found
     */
    public static int of(int[] arr, int x) {
        int low = 0, high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (arr[mid] > x) {
                high = mid - 1;
            } else if (arr[mid] < x) {
                low = mid + 1;
            } else {
                if (mid == arr.length - 1 || arr[mid + 1] != arr[mid]) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

    /**
     * <b>Flow:</b>
     * <p><b>Recursive Implementation</b></p>
     * <p>We used recursive binary search, the problem gets tricky when the element
     * we want to find also exists after we found with mid index.
     * So, we need to make some changes in our binary search implementation,
     * if there is a match for mid index:</p>
     * <p>
     *     <ul>
     *         <li>
     *             check if mid == arr.length - 1 or check if next mid index element is not equal
     *             to current mid index element (arr[mid + 1] != arr[mid]), if either of the
     *             case matches return mid
     *         </li>
     *         <li>
     *             else, check in the right half of the array (repeat).
     *         </li>
     *     </ul>
     * </p>
     * @param arr integer array
     * @param low start index
     * @param high end index
     * @param x element to search
     * @return index of the given element or -1 if not found
     */
    public static int of(int[] arr, int low, int high, int x) {
        if (low > high) return -1;

        int mid = (low + high) / 2;

        if (arr[mid] > x) {
            return search(arr, low, mid - 1, x);
        } else if (arr[mid] < x) {
            return search(arr, mid + 1, high, x);
        } else {
            if (mid == arr.length - 1 || arr[mid + 1] != arr[mid]) {
                return mid;
            } else {
                return search(arr, mid + 1, high, x);
            }
        }
    }
}

Time Complexity: O(log n), Auxiliary Space: O(1) for iterative implementation, O(log n) for recursive implementation as it involves function call overhead.