Проще говоря, производительность с использованием Arrays.binarySearch() сравнима с использованием итеративного цикла (через все элементы массива - линейный поиск), чтобы найти значение в массиве или массиве ArrayList? Может ли конечный пользователь когда-либо увидеть какие-либо задержки с помощью?BinarySearch vs For loop
Также есть ли какие-либо конкретные ситуации, когда один метод лучше другого?
Двоичный поиск происходит в O (log (n)) времени. Линейный поиск (т. Е. Итерация всего массива) происходит в O (n) времени. Есть огромный преимущества в использовании двоичного поиска, когда и где вы можете.
В целом, ситуации, в которых вы должны использовать двоичный поиск, - это когда вам гарантировано, что данные, которые у вас есть, отсортированы и находятся выше некоторой минимальной суммы (поскольку вы не заметите большого повышения производительности, повторно поиск 5 элементов с линейным или двоичным поиском).
Обратите внимание, что Arrays#binarySearch работает только с массивами, а не ArrayList - это принципиально разные объекты. Если вам нужен бинарный поиск в коллекции List, воспользуйтесь Collections#binarySearch().
При условии, что массив отсортирован, и для определенного минимального размера. – towr
Это требование к бару для алгоритма бинарного поиска. Но да. – Makoto
Спасибо за ваш ответ, это полезно. Вы упомянули, что данные должны быть отсортированы, поэтому какой эффект имеет использование «Arrays.sort()» на этом сопоставлении производительности. Кроме того, массив, вероятно, будет когда-либо только около 200 записей, поэтому я не предполагаю, что производительность будет такой заметной. – Andy
Для двоичного поиска требуется сортировка массива/списка. Это необходимо учитывать перед выполнением такого поиска.
Преимущество двоичного поиска в том, что наихудшее время выполнения программы - O (log (n)). С другой стороны, наихудший случай для итеративного поиска - O (n), независимо от того, был ли он отсортирован. В зависимости от размера массива/списка и данных и его квалификации для заказа пользователь может заметить или не заметить разницу в производительности.
Это полностью зависит от данных. Во-первых, ваш массив нужно сортировать. Если ваш массив очень мал, вы можете не заметить существенной разницы.
Если ваш массив очень большой и отсортированный, вы увидите значительное увеличение скорости при использовании двоичного поиска.
Примечание: Поскольку ваш набор данных увеличивается, бинарный поиск становится все быстрее. Это связано с природой роста линейных и логарифмических алгоритмов.
Бинарные поисковые работы для коллекций (ArrayList - это реализация). Метод находится в java.util.Collections
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)`
Вашего классе элемента должен реализовывать Comparable интерфейс и реализовать public int compareTo(T o); метод
Если массив отсортирован, то вы должны использовать бинарный поиск это будет очень полезно и быстро в исполнении со сложностью времени из O (logn), а в случае массива вы должны вызвать Arrays.binarySearch(), и в случае какой-либо коллекции это может быть список или набор, которые вы должны вызвать. Метод binarySearch
@ Энди это хорошо для тебя – Tenacious
http://en.wikipedia.org/wiki/Binary_search_algorithm –
NB двоичный поиск ca n и должно быть выполнено итеративно/с использованием цикла. Я предполагаю, что вы имеете в виду линейный поиск, где каждый элемент списка проверяется до совпадения, если он найден. – delnan
@ delnan Да, вы поняли правильно. Я отредактирую свой вопрос – Andy