CODEWITHSUNDEEP
javaarraylistcontainsbinary-search
John Roberts
John Roberts

Reputation: 5976

Does the contains() method in Java ArrayList use binary search?

Does the contains() method in Java ArrayList use binary search? Or do I need to use Collections to do this instead?

Upvotes: 4

Views: 3578

Answers (4)

samba
samba

Reputation: 2273

No, you need to use Collections to use binary search, usually after sorting it.

Upvotes: -2

Denys Séguret
Denys Séguret

Reputation: 382274

No, it would mean adding a overhead at each insertion so it's not included.

Here's the source code : it just tests all values :

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     }

Upvotes: 1

Puce
Puce

Reputation: 38142

No, it doesn't use binary search as lists don't have to be sorted.

Use the utility methods of the Collections class to first sort the list and then to perform a binary search.

Upvotes: 2

Louis Wasserman
Louis Wasserman

Reputation: 198211

No, you need to use Collections to use binary search, usually after sorting it. An ArrayList doesn't know anything about its ordering, and you have to know a list is sorted before you can use binary search.

Alternately, you could use TreeSet, which is as efficient as using a binary search.

Upvotes: 9

Related Questions