Search Algorithm - Binary Search Enhanced

Abstract

In the previous binary search code, we could only find the index of a single target. In this article, we will enhance this function to make it capable of finding all matching result indices.

Code

/**
 * Recursive binary search algorithm to find the multiple target element in a sorted array.
 *
 * @param arr    The sorted array to search within
 * @param left   The left pointer (start index of the search range)
 * @param right  The right pointer (end index of the search range)
 * @param target The element to search for
 * @return The index of the target element if found, or -1 if not found
 */
public static ArrayList<Integer> binarySearchImproved(int[] arr, int left, int right, int target) {
    // Calculate the middle index and value
    int mid = (left + right) / 2;
    int midVal = arr[mid];

    // Check if the left pointer has crossed the right pointer (base case for termination)
    if (left > right) {
        return null; // Target element not found
    }

    // Compare the target with the middle value
    if (target > midVal) {
        // If the target is greater, search the right half of the array
        return binarySearchImproved(arr, mid + 1, right, target);
    } else if (target < midVal) {
        // If the target is smaller, search the left half of the array
        return binarySearchImproved(arr, left, mid - 1, target);
    } else {
        // Initialize a list to store indices of matching target elements
        ArrayList<Integer> resultIndexList = new ArrayList<>();

        // Search for matching elements to the left of the mid-index
        int temp = mid - 1;
        while (true) {
            if (temp < 0 || arr[temp] != target) {
                break; // Exit the loop if no more matching elements to the left
            }
            resultIndexList.add(temp);
            temp--;
        }

        // Add the current mid-index to the list
        resultIndexList.add(mid);

        // Search for matching elements to the right of the mid-index
        temp = mid + 1;
        while (true) {
            if (temp >= arr.length || arr[temp] != target) {
                break; // Exit the loop if no more matching elements to the right
            }
            resultIndexList.add(temp);
            temp++;
        }

        // Return the list of indices where the target element was found
        return resultIndexList;
    }
}