algorithm - 如何在O（logn）中查找排序数组中数字的出现次数

Question

我有一个排序的整数数组。给定一个数字，即使在最坏的情况下，如何在 O(logn) 中找到该数字的出现次数。

Answer 1

对左侧所有元素都小于您的数字且所有右侧都等于或大于的点进行一次二分搜索，并对所有元素小于或等于左侧且右侧大于的点进行一次二分搜索。

换句话说：在一个搜索中，您的“测试”是<，而在另一个搜索中，测试是<=。

两个搜索都是log n，所以这是您的总数。

例如，在 C++ 中，您需要的两个函数是std::lower_bound和std::upper_bound- 似乎现有的 Java 二进制搜索函数（在 Collections 上）总是试图寻找一个特定的值，所以如果你是，你可能必须自己实现搜索使用那个。

使用仅使用二进制谓词的二进制搜索变体很重要！如果您使用一个变体来检查它是否“意外”地击中了一个特定的键，那么对于这个特定的任务，有时会过早终止。

Answer 2

对数字进行二进制搜索，然后对运行的开始和结束进行二进制搜索。

Answer 3

number + 0.5搜索和number - 0.5使用两个二分搜索的插入点。列表中具有值的元素的数量number是这两个插入点的位置（索引）之差。

Answer 4

按原样运行下面的函数一次，并将 if 条件更改为 if(a[mid]<=val) 并在递归调用中进行相应的更改。返回的两个值是特定值的开始和结束出现。

      int  binmin(int a[], int start, int end,int val )
        {
         if(start<end)
            {
            int mid = (start+end)/2;
            if(a[mid]>=val)
            {
                binmin(a,start,mid-1,val);
            }
            else if(a[mid]<val)
            {
                binmin(a,mid+1,end,val);
            }

    }
    else if(start>end)
            return start;



  }