CODEWITHSUNDEEP
javaalgorithmsearchsorting
Baversjo
Baversjo

Reputation: 3716

Best way to find value in List when list is sorted

Let's say I have a Java ArrayList, that is sorted. Now I would like to find the index of value x. What would be the fastest (without more than 30 lines of code) way to do this? Use of the IndexOf() method? Iterate through all values in a simple for loop? Use of some cool algorithm? We are talking about around let's say 50 integer keys.

Upvotes: 1

Views: 3077

Answers (4)

Matthew Flaschen
Matthew Flaschen

Reputation: 284816

tvanfosson is right, that the time for either will be very low, so unless this code runs very frequently it won't make much difference.

However, Java has built-in functionality for binary searches of Lists (including ArrayLists), Collections.binarySearch.

Upvotes: 6

user447688
user447688

Reputation: 

import java.util.ArrayList;
import java.util.Collections;

ArrayList myList = new ArrayList();
// ...fill with values

Collections.sort( myList );
int index = Collections.binarySearch( myList, "searchVal" );

Edit: untested code

Upvotes: 2

tvanfosson
tvanfosson

Reputation: 532465

Binary search, but since it's only 50 items, who cares (unless you have to do it millions of times)? A simple linear search is simpler and the difference in performance for 50 items is negligible.

Edit: You could also use the built-in java.util.Collections binarySearch method. Be aware, that it will return an insertion point even if the item isn't found. You may need to make an extra couple of checks to make sure that the item really is the one you want. Thanks to @Matthew for the pointer.

Upvotes: 14

Daniel Brückner
Daniel Brückner

Reputation: 59645

If the keys have a acceptable distribution, Interpolation Search might be very fast way considering execution time.

Considering coding time IndexOf() is the way to go (or a built-in in binary search if availiable for your data type (I am from C# and don't know Java)).

Upvotes: 1

Related Questions