重複の可能性:
配列内の要素のランクを効率的に見つけるには?
要素 A [0 から 15] の配列があり、中央値が A[8..11] の範囲にあることがわかっているとします。A[8..11]から選択して、Aのすべての要素の中央値を見つけるにはどうすればよいですか? そのランクは何になりますか？私はこれについて多くのことを読んできましたが、この特定の質問に対する答えを見つけることができませんでした. どんな助けでも大歓迎です。配列には基本的に2Dポイントが含まれており、ポイントを長方形の領域に分割したいと考えています。
これらの要素のサブセットを観察するだけでは、一連の要素の中央値を知ることはできません。中央値は、セット全体のすべての要素に依存します。
私はあなたができるとは思わない。中央値は、並べ替え時にデータを2つに分割するデータ要素です。
ソートされている場合、それは通常、data[0..15]配列のdata[7]とdata[8]の平均になります。
ソートされていない場合、すべての要素を調べずに見つける方法はありません。
配列を「小さい」値と「大きい」値の2つのセットに分割する場合、最も簡単な方法は配列を並べ替えることです。配列全体を並べ替えたくない場合は、変更されたクイックソートを使用できます。配列を分割したら、中央値を含む配列の半分のみを並べ替えます（パーティションが中央値であることが判明した場合を除く）。その場合は停止できます）。