Question

Given a sorted array with lot of duplicates, write a problem to search specific element m. If it’s included in the A, return its minimal index, otherwise return -1. For example A = {0, 0, 1, 1, 1, 2, 3, 3, 4, 4, 4, 4, 4}, if we search 4, you program should return 8. You are only allowed to use binary search. Linear search is not allowed here.

Answer 1

class BinarySearch {
    // Returns index of x if it is present in arr[l..
    // r], else return -1
    public static int binarySearch(int arr[], int l, int r, int x)
    {
        if (r >= l) {
            int mid = l + (r - l) / 2;

            // If the element is present at the mid index
            if (arr[mid] == x)
                return mid;

            // If element is smaller than mid, then it can only be present in left subarray
            if (arr[mid] > x)
                return binarySearch(arr, l, mid - 1, x);

            // Else the element can only be prese in right subarray
            return binarySearch(arr, mid + 1, r, x);
        }

        //element is not present
        return -1;
    }
    
    // modified method to search element in duplicate array
    public static int[] binarySearchDuplicate(int[] array, int l, int r, int n){
        int firstMatch = binarySearch(array, 0, array.length - 1, n);
        int[] resultArray = { -1, -1 };
        
        // element not found
        if (firstMatch == -1) {
            return resultArray;
        }
        
        int leftMost = firstMatch;
        int rightMost = firstMatch;

        for (int result = binarySearch(array, 0, leftMost - 1, n); result != -1;) {
            leftMost = result;
            result = binarySearch(array, 0, leftMost - 1, n);
        }

        for (int result = binarySearch(array, rightMost + 1, array.length - 1, n); result != -1;) {
            rightMost = result;
            result = binarySearch(array, rightMost + 1, array.length - 1, n);
        }

        resultArray[0] = leftMost;
        resultArray[1] = rightMost;
        
        // return the array that has all indices where number can be found
        return resultArray;
    }

    // Driver method to test above
    public static void main(String args[])
    {
        int arr[] = {0, 0, 1, 1, 1, 2, 3, 3, 4, 4, 4, 4, 4};
        int n = arr.length;
        int x = 3;
        int[] result = binarySearchDuplicate(arr, 0, n - 1, x);
        if (result[0] == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at index " + result[0]);
    }
}

FOR HELP PLEASE COMMENT.
THANK YOU