有效地查找已排序数组中的整数量

Question

我正在学习考试,并发现了这个问题.

您将获得一个排序的整数数组,例如:

{-5, -5, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 67, 67, 99}

写一个方法:

Public static int count (int[] a, int x)

返回数字'x'在数组中的次数.

例如:

x = -5, it returns 2
x = 2, it returns 5
x = 8, it returns 0

我需要尽可能高效地写它,请不要给我答案(或者如果你愿意的话写下来,但我不会看),我的想法是做二分搜索,然后去两边(向后)我找到的值和索引号,返回正确的答案,我的问题是:

1. 这是最有效的方式吗？
2. 在最坏的情况下,它不会是O(n)吗？(当数组填充一个数字时) -

如果是这样 - 那我为什么要进行二分搜索呢？

Answer 1

修改二进制搜索以查找给定输入的第一个和最后一个匹配项,然后这两个索引之间的差异就是结果.

要使用二进制搜索查找第一个和最后一个匹配项,您需要更改通常的二进制搜索算法中的位.在二进制搜索中,找到匹配项时返回值.但是,与通常的二进制搜索不同,您需要继续搜索,直到发现不匹配为止.

有用的网址

找到最后一次出现, 找到第一次出现

有点更新

在找到第一个匹配项后,您可以使用该索引作为下一个二进制搜索的起点来查找最后一个.

Answer 2

有两种解决方案：

1）可以执行Binary Search，但是要保持发现第一次出现的不变性。然后进行线性搜索。这将是Theta（log n + C），其中C是计数。

乔恩·本特利（Jon Bentley）的《编程珍珠》（Programming Pearls）写的很好，他提到寻找首次发生实际上比寻找任何发生更为有效。

2）您还可以进行两个二进制搜索，一个用于第一次出现，一个用于最后一次，并取下索引的差。这将是Theta（log n）。

您可以根据C的期望值决定采用哪种解决方案。如果C = o（log n）（是o小），则寻找第一个出现的位置并进行线性搜索会更好。否则，进行两个二进制搜索。

如果您不知道C的期望值，那么使用解决方案2可能会更好。

Answer 3

二元搜索找到第一次出现.进行二分查找以找到最后一次出现.出现次数等于找到的2个索引之间的数字数.

工作代码:

public class Main {
    public static void main(String[] args){
        int[] arr = {-5, -5, 1, 1, 1, 1, 1, 1, 
                                    1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 67, 67, 99};
        int lo = getFirst(arr, -5);
        if(lo==arr.length){ // the number is not present in the array.
            System.out.println(0);
        }else{
            int hi = getLast(arr, -5);
            System.out.println((hi-lo+1));
        }
    }

    // Returns last occurence of num or arr.length if it does not exists in arr.
    static int getLast(int[] arr, int num){
        int lo = 0, hi = arr.length-1, ans = arr.length;
        while(lo<=hi){
            int mid = (lo+hi)/2;
            if(arr[mid]==num){
                ans = mid;
                lo = mid+1;
            }else if(arr[mid]<num){
                lo = mid+1;
            }else if(arr[mid]>num){
                hi = mid-1;
            }
        }
        return ans;
    }

    // Returns first occurence of num or arr.length if it does not exists in arr.
    static int getFirst(int[] arr, int num){
        int lo = 0, hi = arr.length-1, ans = arr.length;
        while(lo<=hi){
            int mid = (lo+hi)/2;
            if(arr[mid]==num){
                ans = mid;
                hi = mid-1;
            }else if(arr[mid]<num){
                lo = mid+1;
            }else if(arr[mid]>num){
                hi = mid-1;
            }
        }
        return ans;
    }
}