Best way to find value in List when list is sorted

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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)).

Answer 4

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