Index of First Occurrence in Sorted Array

Problem: Given a sorted array with repetition and an element x, we need to find index of first occurrence of x/

Examples:

Input: arr[] = {1, 10, 10, 10, 20, 20, 40}, x = 20
Output: 4

Input: arr[] = {10, 20, 30}, x = 15
Output: -1

Input: arr[] = {15, 15, 15}, x = 15
Output: 0

Naive solution is to use Linear Search 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.

For example, look at the below array:

arr[] = {5, 10, 10, 20, 20}, x = 10
here, low (index) = 0, high (index) = 4; so mid = (0+4)/2 = 2, so arr[mid] is 10 and index is 2, but we also have 10 at index 1

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

• check if mid == 0 or check if previous mid 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 left half of the array (repeat).

Solution:

package com.raindroplabs.searching;

/**
 * <p><b>First Occurrence:</b> is to find index of first 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[] firstOccNums = {5, 10, 10, 20, 20};
 * FirstOccurrence.of(firstOccNums, 10);
 * FirstOccurrence.of(firstOccNums, 0, firstOccNums.length, 10)
 * }
 */
public class FirstOccurrence {

    /**
     * <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 == 0 or check if previous 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 left 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 == 0 || arr[mid - 1] != arr[mid]) {
                    return mid;
                } else {
                    high = 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 == 0 or check if previous 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 left 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 (x > arr[mid]) {
            return search(arr, mid + 1, high, x);
        } else if (x < arr[mid]) {
            return search(arr, low, mid - 1, x);
        } else {
            if (mid == 0 || arr[mid - 1] != arr[mid]) {
                return mid;
            } else {
                return search(arr, low, mid - 1, 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.