Have Geek Brain

Best way to find value in a list when the list is sorted

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

+1


a source to share


4 answers


Binary search , but since there are only 50 items that care (unless you have to do it millions of times)? Simple linear search is simpler and the performance difference for 50 items is negligible.



Edit . You can also use the built-in java.util.Collections binarySearch method . Be aware that it will return the insertion point even if the element is not found. You may need to do a couple more checks to ensure that the item is indeed the item you want. Thanks @Matthew for the pointer.

+14


a source


tvanfosson is right that the time will be very low for both, so if this code runs very often it won't matter much.



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

+6


a source 


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

+2


a source


If the keys have a reasonable distribution, Interpolation Search can be very fast considering the execution time.

Considering coding time IndexOf()

- this is the way to go (or built into binary search if available for your datatype (I'm from C # and don't know Java)).

+1


a source






More articles:


All Articles