アレイは見つかったにもかかわらず「見つからない」と報告する: 混乱を招く検索のジレンマ

Question

これは、さまざまな言語の新人プログラマーからの多くの質問で見られる、論理エラーを含む一般的な質問と回答です。

問題は、配列内で特定の入力条件に一致する要素を検索することです。アルゴリズムの擬似コードは次のとおりです:

リーリー

このコードでは、一致する要素が正常に見つかった場合でも、「見つかりません」と報告されます。

Answer 1

問題は、配列内で何かを線形に検索する場合、配列の最後に到達するまで、それが見つからなかったことに気づかないことです。質問内のコードは、他に一致する要素がある場合でも、一致しない要素ごとに「見つかりません」と報告します。

簡単な変更は、変数を使用して何かが見つかったかどうかを追跡し、ループの最後でその変数をチェックすることです。

リーリー

Python の for ループには else: ブロックがあります。コードは、break を使用してループが終了したときではなく、ループの実行が終了したときにのみ実行されます。これにより、found 変数を回避できます (ただし、後の処理では役立つ可能性があります):

リーリー

一部の言語には、独自のループを作成する代わりに使用できる組み込みメカニズムがあります。

• 一部の言語には、コールバック関数を受け入れ、配列の要素に対して関数が成功したかどうかを示すブール値を返す any または some 関数があります。
• 言語に配列フィルタリング機能がある場合は、条件をチェックする関数を使用して入力配列をフィルタリングし、結果が空の配列かどうかをチェックできます。
• 要素を正確に一致させようとしている場合、ほとんどの言語では、一致する要素を検索するための find または index 関数が提供されています。

頻繁に検索を行う場合は、配列をより効率的に検索できるデータ構造に変換することをお勧めします。ほとんどの言語は、sets および/または hashtables データ構造を提供します (後者には、連想配列、マップ、辞書など、言語に応じて多くの名前があります)。通常、これらがその構造です。検索が行われる場所は O(1) ですが、配列をスキャンする時間は O(n) です。