この検索のパフォーマンスを改善しますか？

Question

次の検索を高速に行う方法はありますか？ A配列の項目は、DESCの順序でソートされます。

Answer 1

あなたはあなたのケースでstd::lower_boundアルゴリズムを使用することができます

int left = 0; 
int right = items_no; // Exclusive 
while (left < right) { 
    int mid = (left + right)/2; 

    if (value == A[mid]) 
     return mid; 
    if (value < A[mid]) { 
     left = mid + 1; 
    } else { 
     right = mid; 
    } 
} 
return only_exact_match ? -1 : right - 1; // The greater 

Answer 2

あなたの配列はソートされているので、二等分に類似したステップで検索することができます。まず、あなたの価値に対して中点をチェックしてください。それが等しいなら、あなたはあなたの答えを持っています。値が大きければ、値は配列の下半分になります。そうでない場合、あなたの価値は上半分にあります。値を見つけるまで、または要素がなくなるまで、配列の残りの要素を二等分することによって、このプロセスを繰り返します。 2番目のif節について、一致する値が見つからない場合、要素i + 1が存在する場合（すなわち、配列の最後にない場合）、最も近い小さい要素が要素i + 1になります。

Answer 3

バイナリ検索。他の人が書いたように、O（log N）でバイナリ検索を実行します。これは次のようなものになります。

int find_pos(int A[], int value, int items_no, bool only_exact_match) 
{ 
    const int *pos_ptr = std::lower_bound(A, A + items_no, value, std::greater<int>()); 
    const ptrdiff_t pos = pos_ptr - A; 

    if (pos >= items_no) 
     return -1; 
    if (*pos_ptr != value && only_exact_match) 
     return -1; 
    return pos; 
}