ソートされた配列に何回xが現れるかを調べる効率的なアルゴリズム

Question

ソートされたn個の整数値と整数xの配列が与えられました。この配列に何回xが現れるかを調べるのに最も効率的なアルゴリズムは何でしょうか？

私はバイナリ検索を考えましたが、xになったときに左と右に分割して、xを追加するかどうかを確認しましたが、これに対して他の解決方法があるかどうかを知りたいと思っていました。

Answer 1

アレイ内のxの出現数が配列の長さと比較して定数であると考えられる場合、バイナリ検索のアプローチではO(log(N)というアルゴリズムが得られますが、それ以上はできません。

たとえば、配列のすべての要素がxである場合、または要素の半分がxの場合、アルゴリズムの第2部分（split left and right to see if there is more x to add to my count）は線形時間がかかります。

2つ以上のバイナリを検索して、配列内の最初のxと最後のxのインデックスを検索することを避けることができます。たとえば、x-1とx + 1でバイナリ検索を実行する（これがint配列であると仮定して）ことができます。

これは、配列内に何個のxがあるかにかかわらず、O（log（N））の実行時間を与えます。

Answer 2

これは動作するはずです。

public class Numbers{ 

    public static void main(String[] args){ 
     int[] x = new int[]{1,2,3,4,8,7,6,7,7,7,5}; 
     int number = 0; 
     for (int i = 0; i < x.length; i++){ 
      if (x[i] == n){ 
       number++; 
      } 
     } 
     System.out.println(number); 
    } 

} 

x - arrayタイトル; n - あなたが言及したxの整数。

Answer 3

それは整数であり、リストはソートされます。

あなたは、インデックスで分割分割検索アルゴリズムを使用します。

indexToSplit = (int) x*(an - a1)/n 

：

x is your integer to find 
an is the last integer in the list 
a1 is the first integer in the list 
n is the size of the list 

はあなたのリストは、最低から最高

にこれはヒューリスティックでソートされていると仮定すると、はバイナリソートより優れていますが、リスト内の整数がどれくらい一様に分布しているかによって異なります