のは、以下が真であるとしましょう:連想配列に番号の最初の出現を検索
- 私は要素の未知数を含む連想配列を持っています。
- 鍵は整数で、
1
から始まり、それぞれが最後のものより1つ多くなります。 - キーがNの要素があり、値は
1
です。 - キーがN未満の各要素の値は、
0
です。 - より大きいキーを持つ各要素の値Nは、
1
です。
これは配列です:
質問です: 配列の最初の「1」の位置を見つけるための最速/賢い方法は何ですか?
のは、以下が真であるとしましょう:連想配列に番号の最初の出現を検索
1
から始まり、それぞれが最後のものより1つ多くなります。1
です。0
です。1
です。これは配列です:
質問です: 配列の最初の「1」の位置を見つけるための最速/賢い方法は何ですか?
あなたが本当に配列(非常に奇妙な状況)の長さがわからない場合は、おそらくあなたが行うことができ、すべてはすなわちなど、16をスキップし、8をスキップし、4をスキップし、幾何学的に検索を育てるありますあなたが1を見つけるまでは、(幾何学的)バイナリ検索で元に戻します。
これは幾何学的な成長によるバイナリ検索以外の方法ではありませんか? –
私はまだこの配列の長さを知ることができませんでしたが、それが本当に不明な場合は、それを無限の数列と考えています。シーケンスが増加するだけで(> =)、それは助けにならないことがわかります。ゼロのシーケンスは、宇宙と同じ長さにすることができます。文字どおり、理論的には、これをどのような方法でも最適化することはできません。さて、システムの最大インデックス(たとえばINT_MAX)をバインドし、そのようなバイナリ検索を考慮することができます。 –
私は仕事の面接で得た質問です。彼らが私に言ったことです。 –
array_search
はあなたの最善の策
// Make up some data...
$data = [];
for ($i = 1; $i <= 20; ++$i) {
$data[$i] = rand(0,5);
}
var_dump($data);
// Find the first one...
echo 'The first 1 is at position: ' . array_search(1, $data);
ですが、私が間違っていないよ場合は、バイナリサーチは、配列の長さを知るために私を必要とし、ここで私はそれは長さだか分かりません。 –
私は仕事の面接で得た質問です。彼らが私に言ったことです。 –