java - 使用二分查找查找数字的最大索引出现次数

Question

此代码生成一个随机数，按升序对其进行排序，并进行二分搜索以查找目标值。我的问题是如何修改此代码以找到给定目标的最大索引。例如数组有 { 1, 2 , 3, 5, 5, 5, 5}，目标是 5，所以输出应该是 6 而不是 3。谢谢。

    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

您可以通过修改二分搜索算法代码来做到这一点，如下所示:

 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;
    }
}

此代码而是搜索第一个大于键的数字。可以是任何数字，6 或 10000，这并不重要。正如你所看到的，如果 arr[mid] 等于 key，代码仍然会在区间 [mid, hi] 上运行。为什么这两个最后会返回？好吧，如果输入数组与您给出的数组类似，则 lo 最终将是最后 5 个数字的索引，但如果我们在输入数组的末尾添加另一个数字，则 lo 将是最后 5 个数字后面的索引。因此，我们有 2 种不同的情况。

此外，您不能像其他答案一样使用线性循环来完成此操作，因为这会将算法减少到 O(n)，并且最终只是在简化数组上进行线性搜索。