c++ - DynamicArrayListの線形およびバイナリ検索

Question

ねえ、私は動的配列リストをやっていて、配列リストの線形および二分探索を行う方法と、これらの検索の長所と短所は何ですか？

Answer 1

これらを拡張配列として実装していると推測すると、部屋が足りなくなったときに新しい配列を再割り当てしてから、要素をコピーします。

この場合、あなたの質問は、この配列に対して線形および二分探索を実装する方法に帰着しますか？

その場合、オンラインで見つけられるたくさんの記事、サンプルがあります。

線形検索の利点は、小さな配列の場合、速度に違いがなく、探しているアイテムが配列内にある限り、ソートされていない配列で常に機能するという事実です。

これは、大きな配列では非常に高速な二分探索とは対照的ですが、小さなサイズの配列では、線形探索に比べて実際のパフォーマンス上の利点はありません。このスピードアップには、この利点を得るためにソートする必要があるという犠牲が伴います。