Find the largest index occurrence of a number using binary search

Question

This code, generates a random number, sorts it in ascending order and does the binary search to find a target value. MY QUESTION IS HOW DO I MODIFY THIS CODE TO FIND THE LARGEST INDEX OF THE GIVEN TARGET. For example the array has { 1, 2 , 3, 5, 5, 5, 5}, the target is 5, so the output should be 6 instead of 3. Thankyou.

    import java.util.*;
    public class Sort
    {
        public static void main(String args[])
        {
            Scanner in = new Scanner(System.in);
            System.out.print("How many numbers do you want? ");
            int howMany = in.nextInt();
            int [] myArray =  getSortedRandomArray(howMany);
            System.out.print("\nFor what value would you like to search? ");
            int target = in.nextInt();
            int index = bsearch ( myArray, target);
            if (index >= 0)
            {
                System.out.println("The value " + target + " occurs at index " + index);
            }
            else
            {
                System.out.println("The value " + target + " does not occur in the array. ");
            }   
        }

  public static int bsearch(int[] arr, int key)
    {
    int lo = 0, hi = arr.length - 1;
    {
        while (lo < hi) 
        {
            int mid = (lo + hi) / 2;
            if (arr[mid] <= key)
                lo = mid + 1;
            if (arr[mid] > key)
                hi = mid;
        }
        if (arr[lo] == key) {
            return lo;
        }
        else if ((arr[lo] != key) && (arr[lo-1] == key)){
            return lo - 1;
        }
        else{
        System.out.print("The value " + key + " does not occur in the array. "); 
    } 
        return -1 ;
    } 
   public static int[] getSortedRandomArray (int howMany)
    {
        int[] returnMe = new int [howMany];
        Random rand = new Random();
        for (int i = 0; i < howMany ; i++) 
            returnMe[i] = rand.nextInt(Integer.MAX_VALUE) + 1;
        for (int i = 1; i <= (howMany - 1); i++)
        {
            for (int j = 0; j <= howMany - i -1; j++)
            {
                int tmp = 0;
                if (returnMe[j] > returnMe[j+1])
                {
                    tmp = returnMe[j];
                    returnMe[j] = returnMe[j + 1];
                    returnMe[j + 1] = tmp; 
                }   
            }  
        }
        System.out.print("Here is a random sorted array: ");
        for ( int i = 0; i < howMany; i++)
            System.out.print(returnMe[i] + " ");     
        return returnMe;
    }

Answer 1

You can do this by modifying the binary search algorithms code like this:

 public static int bsearch(int[] arr, int key) {
    int lo = 0, hi = arr.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] <= key)
            lo = mid + 1;
        if (arr[mid] > key)
            hi = mid;
    }

    if (arr[lo] == key) {
        return lo;
    }
    else {
        return lo - 1;
    }
}

This code instead searches for the first number larger than key. That can be any number, 6 or 10000, it doesn't matter. As you can see, if arr[mid] is equal to key, the code will still run on the interval [mid, hi]. Why those two returns at the end? Well if input array is like the one you gave, lo will end being the index of the last 5, but if we add another number at the end of input array, lo will be index of the number behind the last 5. Therefore, we have 2 different cases.

Also, you can't do it with a linear loop like other answers, because that reduces the algorithm to O(n) and it ends just being a linear search on a reduced array.

Answer 2

If you update your bsearch algorithm a little you can ask it to seek higher matches recursively. However whether this is more efficient than a linear loop would depend on what the input array looked like.

public static int bsearch(int[] arr, int key, int lo, int hi) {
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == key) {
            System.out.println("The value " + key + " is found at " + mid);
            int higherResult = bsearch(arr, key, mid + 1, hi);
            if (higherResult < 0) {
                return mid;
            }
            return higherResult;
        }
        if (arr[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}