CODEWITHSUNDEEP
javaandroidarraylist
Lefteris
Lefteris

Reputation: 14677

Optimal way to search an ArrayList of Integers in Android

I have an ArrayList of integers.

Let's say for example an ArrayList with the integers 0,4,7,10

I want now to compare any given integer and see in which position it is on the ArrayList.

So for example, if my integer is 3, it should be between 0 and 4, so the result will be 1. If my integer is 9 it will be between 7 and 10, so my result will be 3.

Obviously I can loop through the entire ArrayList, like this:

    int indexOfItem = 0;
    if (mylist.size()>0)
        while (indexOfItem<mylist.size() && integerImSearching>mylist.get(itemsToSkip)) {
            indexOfItem++;          
        }

And I can get the Index of my item from this method. But while this is fine, if the ArrayList is small, I'm afraid it's not the optimal way if the list is rather large. Is there a better way to achieve this ?

Upvotes: 0

Views: 176

Answers (1)

C. K. Young
C. K. Young

Reputation: 223003

Since your ArrayList contents are sorted, you should use Collections.binarySearch to locate your item. This will make each search O(log n) instead of O(n).

This function return the index of the item, if found, or else the ones' complement of its insertion position. So, for your purposes, you can do this:

int lowerBound(List<Integer> list, int item) {
    int result = Collections.binarySearch(list, item);
    return result >= 0 ? result : ~result;
}

Upvotes: 5

Related Questions