java - Java ArrayList の contains() メソッドは二分探索を使用しますか?

Question

Java ArrayList の contains() メソッドは二分探索を使用しますか? または、代わりにコレクションを使用してこれを行う必要がありますか?

Answer 1

Collectionsいいえ、バイナリ検索を使用するには、通常はソート後に使用する必要があります。anArrayListはその順序について何も知りません。二分探索を使用する前に、リストがソートされていることを知っておく必要があります。

TreeSetまたは、二分探索を使用するのと同じくらい効率的な を使用することもできます。

Answer 2

いいえ、リストをソートする必要がないため、バイナリ検索は使用しません。

Collections クラスのユーティリティ メソッドを使用して、最初にリストを並べ替え、次にバイナリ検索を実行します。

Answer 3

いいえ、挿入ごとにオーバーヘッドを追加することを意味するため、含まれていません。

ソースコードは次のとおりです。すべての値をテストするだけです：

218     public boolean contains(Object o) {
219         return indexOf(o) >= 0;
220     }

229     public int indexOf(Object o) {
230         if (o == null) {
231             for (int i = 0; i < size; i++)
232                 if (elementData[i]==null)
233                     return i;
234         } else {
235             for (int i = 0; i < size; i++)
236                 if (o.equals(elementData[i]))
237                     return i;
238         }
239         return -1;
240     }