2

整数の配列でX未満の最初の数値を見つけるアルゴリズムを探しています。実際、私は線形検索を使用していますが、バイナリ検索の方が良いかもしれないと思います（以前にすでに見たように）が、自分で実装する方法がわかりません（最初のものを見つけるために変更されたバージョンを実装しないでください-より少ないバツ）。ビン検索より良いものがあれば教えてください。この配列は、プログラムの実行中に非常に多くのアクセスと変更が行われるため、必要です。

現在の（重要な）実装は次のとおりです。

int findmin(int *arr,int n,int size)
{
  int i;
  for(i = 0; i < size && arr[i] < n; i++)
    ;
  return i-1;
}

このインデックスは、特定のインデックスにN値を挿入する関数のパラメータ入力として使用されます。この関数のインデックスであり、配列に数値を挿入しますが、新しい数値が挿入されるたびに、sort（）呼び出しなしでソートされます。これは、関連するファイルテキストの解析であり、多くのファイルを解析し、かなりの数の文字を解析します。私は物事をできるだけ速くするためにいくらかの努力をする必要があります（私の文脈と知識において）。

編集：新しい番号を挿入した後でも、配列は常に並べ替えられます。

4

2 に答える 2

2

N個の要素の配列がすでにソートされている必要があります。

「高」をNに、「低」を-1に設定します。

「プローブ」要素N/2（intに切り捨て）。

プローブされた要素がターゲットよりも小さい場合は、「high」をN/2に設定します。>の場合、「低」をN/2に設定します。（もちろん、==の場合、あなたはあなたの答えを持っています。）

「低」と「高」の中間を調べて、繰り返します。

心配する必要のある境界条件がありますが、それほど複雑ではありません。

于 2013-03-19T02:09:05.377 に答える
2

ここでは二分探索は問題ありません。難しいのは、境界条件を確認する方法と、どの値を返すかです。さらに、重複する値に注意する必要があります。次の機能が動作します。

    int binarySearch(int a[], int length, int value)
    {
        if (a[0] > value)
            return -1;

        int low = 0;
        int high = length-1;

        while (low<=high)
        {
            int mid = low+((high-low)/2);

            if(a[mid] >= value)
                high = mid-1;
            else
                low = mid+1;
        }

        return low-1;
    }

テスト:(重複あり）

    int arr[] = {1, 3, 4, 6, 6, 10};
    int length = sizeof(arr)/sizeof(arr[0]);

    int index = binarySearch(arr, length, 6); // will be 2
于 2013-12-20T13:13:05.073 に答える