Java Поиск в массиве для соответствующей строки

Question

как я могу оптимизировать следующее:

final String[] longStringArray = {"1","2","3".....,"9999999"};
String searchingFor = "9999998"
for(String s : longStringArray)
    {
        if(searchingFor.equals(s))
        {
            //After 9999998 iterations finally found it
            // Do the rest of stuff here (not relevant to the string/array)
        }
    }

ПРИМЕЧАНИЕ : longStringArray ищется только один раз за время выполнения, не сортируется и отличается каждый раз, когда я запускаю программу.

Я уверен, что есть способ улучшить производительность в худшем случае, но, похоже, я не могу его найти ...

P.S. Также был бы признателен за решение, где строка searchFor не существует в массиве longStringArray.

Спасибо.

Answer 1

Ну, если у вас есть для использования массива, и вы не знаете, отсортирован ли он, и вы собираетесь выполнить только один поиск, это всегда будет O (N) операция. Вы ничего не можете с этим поделать, потому что любой шаг оптимизации будет, по крайней мере, O (N) для начала - например, заполнение набора или сортировка массива.

Другие опции:

• Если массив отсортирован, вы можете выполнить двоичный поиск. Это превратит каждый поиск в операцию O (log N).
• Если вы собираетесь выполнять более одного поиска, рассмотрите возможность использования HashSet<String>. Это превратит каждый поиск в операцию O (1) (при условии нескольких коллизий).

Answer 2

import org.apache.commons.lang.ArrayUtils;
ArrayUtils.indexOf(array, string);

Документация ArrayUtils

Answer 3

Arrays.asList (longStringArray) .Contains (searchingFor)

Answer 4

Вы можете создать второй массив с хеш-кодами строки и двоичным поиском по ней.

Вам нужно будет отсортировать массив хешей и соответственно переместить элементы исходного массива. Таким образом, вы получите чрезвычайно быстрый поиск, но он будет упорядочен, поэтому для вставки новых элементов требуются ресурсы.

Наиболее оптимальным было бы реализовать двоичное дерево или B-дерево , если у вас действительно очень много данных и вам нужно обрабатывать вставки, это того стоит.