Оптимальный способ поиска ArrayList из целых чисел в Android

Question

У меня есть ArrayList целых чисел.

Скажем, например, в ArrayList с целыми числами 0,4,7,10

Теперь я хочу, чтобы сравнить любое данное число и посмотреть, в каком положении он находится на ArrayList.

Так, например, если мое целое число равно 3, оно должно быть от 0 до 4, поэтому результат будет равен 1. Если мое целое число равно 9, оно будет от 7 до 10, поэтому мой результат будет равен 3.

Очевидно, что я могу перебрать весь ArrayList, как это:

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

И я могу получить индекс моего пункта из этого метода. Но, хотя это прекрасно, если ArrayList мал, я боюсь, что это не оптимальный способ, если список довольно большой. Есть ли лучший способ достичь этого?

Answer 1

Поскольку содержимое вашего ArrayList сортировано, вы должны использовать Collections.binarySearch, чтобы найти свой товар. Это сделает каждый поиск O (log n) вместо O (n).

Эта функция возвращает индекс элемента, если он найден, или же его дополнение к его позиции вставки. Таким образом, для ваших целей, вы можете сделать это:

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