algorithm - O（logn）でソートされた配列内の数値の出現回数を見つける方法

Question

ソートされた整数の配列があります。数値が与えられた場合、最悪の場合でも O(logn) でその数値の出現回数を見つける方法。

Answer 1

左側のすべての要素が数値よりも小さく、右側のすべての要素が等しいか大きい点を 1 回、およびすべての要素が左側より小さく右側が大きい点を 1 回バイナリ検索します。

つまり、ある検索では「テスト」は<であり、別の検索ではテストは<=です。

両方の検索がlog nであるため、それが合計です。

たとえば、C++ で必要な 2 つの関数はstd::lower_bound、およびstd::upper_bound- 既存の Java バイナリ検索関数 (コレクション上) は常に特定の値を検索しようとするようです。それを使って。

二項述語のみを使用する二分探索バリアントを使用することが重要です。「偶然に」特定のキーにヒットしたかどうかをチェックするバリアントを使用すると、この特定のタスクに対してあまりにも早く終了することがあります。

Answer 2

番号を二分探索し、次に実行の開始と終了を二分探索します。

Answer 3

number + 0.5およびの挿入ポイントnumber - 0.5を 2 つのバイナリ検索を使用して検索します。リスト内の値を持つ要素の数はnumber、これら 2 つの挿入ポイントの位置 (インデックス) の差です。

Answer 4

以下の関数をそのまま実行し、if条件をif（a [mid] <= val）に変更して、再帰呼び出しで対応する変更を1回実行します。返される2つの値は、特定の値の開始と終了のオカレンスです。

      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;



  }