#java #list #search #binary
#java #Список #Поиск #двоичный
Вопрос:
использование Java. список отсортирован, поэтому я хочу использовать двоичный поиск. Я бы предпочел не писать дополнительный код, есть ли какой-либо встроенный метод для этого?
Ответ №1:
Вы смотрели Collections.binarySearch ? Это в основном выполняет часть поиска — затем вам нужно будет посмотреть, был ли результат отрицательным (т. Е. Точное совпадение не было найдено) и, если да, использовать побитовое дополнение, чтобы найти, куда был бы вставлен элемент.
Комментарии:
1. что вы подразумеваете под «использовать побитовое дополнение»?
2. О, теперь я вижу это. Я просмотрел Collections.BinarySearch, но не заметил части «точка вставки». Большое вам спасибо!!!
3. О, кстати, я понял, что если в списке есть несколько элементов с одинаковым значением, то BinarySearch не выдаст желаемого результата при поиске этого значения. Я хочу, чтобы индекс первого элемента был равен или больше фактически заданного значения.
4. @Thi: Если могут быть дубликаты, BinarySearch выдаст вам одно из допустимых значений индекса… таким образом, вам захочется посмотреть назад, пока вы не найдете и не проиндексируете с меньшим значением.
Ответ №2:
Попробуйте JavaDocs для массивов, существует около 17 определений функций для binarySearcy()
Также вот несколько реализаций
Редактировать:
Хотя вы сказали, что не хотите писать код, это верный способ получить именно то, что вы хотите. И учитесь по пути 🙂
http://www.java-tips.org/java-se-tips/java.lang/binary-search-implementation-in-java.html http://en.wikibooks.org/wiki/Algorithm_Implementation/Search/Binary_search
Комментарии:
1. Мне нравится название, пришлось посмотреть его значение. 😉
2. Ну, я знаю, вы сказали, что на самом деле не хотели писать новый код. Но, учитывая то, что доступно в api, попробуйте некоторые фрагменты кода, которые я добавил к своему сообщению
3. Здесь мы работаем с отсортированным списком, поэтому я думаю, что было бы логичнее использовать платформу Collections, а не Arrays.
4. 1 Я также согласен с вами, что коллекционирование было бы хорошей идеей. В спецификации BinarySearch указано, что список должен быть отсортирован в порядке возрастания в соответствии с указанным средством сравнения. Отдайте свои баллы @zloster (я еще не пил кофе)