Java поиск значения в массиве

Как определить, содержит ли массив определенное значение в Java?

у меня есть String[] со значениями типа так:

дано String s , есть ли хороший способ проверить, есть ли VALUES содержит s ?

27 ответов

предупреждение: это не работает для массивов примитивов (см. комментарии).

С java-8

теперь вы можете использовать Stream чтобы проверить, является ли массив int , double или long содержит значение (соответственно, используя IntStream , DoubleStream или LongStream )

пример

просто, чтобы очистить код для начала. У нас (исправлено):

это изменчивый статический, который FindBugs скажет вам, очень непослушный. Это должно быть личное:

(обратите внимание, вы можете на самом деле бросить

можно использовать ArrayUtils.contains С Apache Commons Lang

обратите внимание, что этот метод возвращает false Если переданный массив null .

есть методы, доступные для примитивных массивов всех видов.

пример:

Я удивлен, что никто не предложил просто реализовать его по руке:

благоустройство:

на v != null условие является постоянным внутри метода, оно всегда вычисляет одно и то же логическое значение во время вызова метода. Поэтому, если вход array большой, более эффективно оценивать это условие только один раз, и мы можем использовать упрощенное/более быстрое условие внутри for цикл на основе результата. Улучшенное contains() метод:

Если массив не отсортирован, вам придется перебирать все и вызывать equals для каждого.

Если массив отсортирован, вы можете выполнить двоичный поиск, есть один в массивы класса.

вообще говоря, если вы собираетесь сделать много проверок членства, вы можете сохранить все в наборе, а не в массиве.

1) Использование Списка:

2) Использование Set:

3) используя простой цикл:

4) Использование Массивов.binarySearch ():

приведенный ниже код неверен,он указан здесь для полноты. binarySearch () можно использовать только для отсортированных массивов. Вы найдете результат странно ниже. Это лучший вариант, когда массив сортированный.

Пример:

для чего это стоит, я провел тест, сравнивая 3 предложения для скорости. Я сгенерировал случайные целые числа, преобразовать их в строку и добавил их в массив. Затем я искал максимально возможное число / строку, что было бы наихудшим сценарием для asList().содержит.)(

при использовании размера массива 10K результаты где:

при использовании массива 100K результаты где:

поэтому, если массив создается в отсортированном порядке, двоичный поиск является самым быстрым, иначе asList().contains был бы путь пойти. Если у вас много поисков, то, возможно, стоит отсортировать массив, чтобы вы могли использовать двоичный поиск. Все зависит от вашего заявления.

Я думаю, что это результаты, которые большинство людей ожидали бы. Вот тестовый код:

вместо использования синтаксиса инициализации быстрого массива вы можете просто инициализировать его как список сразу аналогичным образом, используя массивы.метод asList например:

тогда вы можете сделать (как указано выше): STRINGS.contains(«the string you want to find»);

С Java 8 вы можете создать поток и проверить, соответствуют ли какие-либо записи в потоке «s» :

или как общий метод:

можно использовать массивы класс для выполнения двоичного поиска значения. Если Ваш массив не отсортирован, вам придется использовать функции сортировки в том же классе для сортировки массива, а затем выполнить поиск по нему.

ObStupidAnswer (но я думаю, что где-то здесь есть урок):

на самом деле, если вы используете HashSet, как предложил том Хотин, вам не нужно беспокоиться о сортировке, и ваша скорость такая же, как и при двоичном поиске по предустановленному массиву, возможно, даже быстрее.

все зависит от того, как настроен ваш код, очевидно, но с того места, где я стою, порядок будет:

на Несортированном массиве:

поиска HashSet
asList
сортировка и двоичный

на сортированном массив:

Так или иначе, HashSet ftw

Если у вас есть библиотека Google collections, ответ Тома можно упростить, используя ImmutableSet (http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/ImmutableSet.html)

Это действительно удаляет много беспорядка из предложенной инициализации

одно из возможных решений:

разработчики часто делают:

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

первый является более читаемым, чем второй.

на Java 8 использовать потоки.

использование простого цикла является наиболее эффективным способом сделать это.

для массивов ограниченной длины используйте следующее (Как указано camickr). Это медленно для повторных проверок, особенно для более длинных массивов (линейный поиск).

для быстрой производительности, если вы неоднократно проверяете против большего набора элементов

массив является неправильной структурой. Используйте TreeSet и добавьте к нему каждый элемент. Он сортирует элементы и имеет быстрый exist() способ (двоичный поиск).

если элементы реализации Comparable и вы хотите, чтобы TreeSet отсортированный образом:

ElementClass.compareTo() метод должен быть совместим с ElementClass.equals() : см.триады не появляются, чтобы сражаться? (Java Set отсутствует элемент)

в противном случае, используйте свой собственный Comparator :

выплата: проверить существование некоторого элемента:

массивы.asList () — > тогда вызов метода contains () всегда будет работать, но алгоритм поиска намного лучше, так как вам не нужно создавать легкую оболочку списка вокруг массива, что и является массивами.asList() делает.

Проверьте, присутствует ли значение в массиве в Java

Для данного массива задача состоит в том, чтобы проверить, присутствует ли определенный элемент в этом массиве или нет в Java.

Читать еще: Java 8 update 45 что это

Примеры:

Ниже приведены различные способы сделать это:

Используя метод линейного поиска :

Пример:

// Java-программа для проверки погоды
// элемент присутствует в массиве или нет

// Функция возвращает true, если данный элемент

// найдено в массиве

private static void check( int [] arr, int toCheckValue)

// проверяем, указан ли элемент

// присутствует в массиве или нет

// используя метод линейного поиска

boolean test = false ;

for ( int element : arr) <

if (element == toCheckValue) <

System.out.println( «Is » + toCheckValue

+ » present in the array: » + test);

public static void main(String[] args)

// Получить проверяемое значение

int toCheckValue = 7 ;

// Проверить, является ли это значение

// присутствует в массиве или нет

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

В этом примере метод Arrays.binarySearch () используется для бинарного поиска.

Пример:

// Java-программа для проверки погоды
// элемент присутствует в массиве или нет

// Функция возвращает true, если данный элемент

// найдено в массиве

private static void check( int [] arr, int toCheckValue)

// сортируем данный массив

// проверяем, указан ли элемент

// присутствует в массиве или нет

// используя метод двоичного поиска

int res = Arrays.binarySearch(arr, toCheckValue);

boolean test = res > 0 ? true : false ;

System.out.println( «Is » + toCheckValue

+ » present in the array: » + test);

public static void main(String[] args)

// Получить проверяемое значение

int toCheckValue = 7 ;

// Проверить, является ли это значение

// присутствует в массиве или нет

Использование List.contains () Метод: метод List () в Java используется для проверки, существует ли указанный элемент в данном списке или нет.

Пример:

// Java-программа для проверки погоды
// элемент присутствует в массиве или нет

// Функция возвращает true, если данный элемент

// найдено в массиве

private static void check(Integer[] arr, int toCheckValue)

// проверяем, указан ли элемент

// присутствует в массиве или нет

// используя метод contains ()

System.out.println( «Is » + toCheckValue

+ » present in the array: » + test);

public static void main(String[] args)

// Получить проверяемое значение

int toCheckValue = 7 ;

// Проверить, является ли это значение

// присутствует в массиве или нет

Использование метода Stream.anyMatch () :
Поток anyMatch (предикат предиката) возвращает, соответствуют ли какие-либо элементы этого потока указанному предикату. Он может не оценить предикат по всем элементам, если в этом нет необходимости для определения результата.

Пример 1. Использование метода Stream.of () для создания Stream

// Java-программа для проверки погоды
// элемент присутствует в массиве или нет

// Функция возвращает true, если данный элемент

// найдено в массиве

private static void check( int [] arr, int toCheckValue)

// проверяем, указан ли элемент

// присутствует в массиве или нет

// используя метод anyMatch ()

.anyMatch(x -> x == toCheckValue);

System.out.println( «Is » + toCheckValue

+ » present in the array: » + test);

public static void main(String[] args)

// Получить проверяемое значение

int toCheckValue = 7 ;

// Проверить, является ли это значение

// присутствует в массиве или нет

Пример 2. Использование метода Arrays.stream () для создания Stream

// Java-программа для проверки погоды
// элемент присутствует в массиве или нет

// Функция возвращает true, если данный элемент

// найдено в массиве

private static void check( int [] arr, int toCheckValue)

Как найти число в массиве?

подскажите пожалуйста как найти максимально и минимальное число в массиве?

за ране спасибо !

17.04.2012, 12:20

Как найти макс. и мин. число в массиве?
Подскажите пожалуйста как найти максимально и минимальное число в массиве? За ране спасибо !

Выяснить, какое число встречается в массиве раньше – число Фибоначчи или простое число
Дан натуральный массив A, состоящий из натуральных чисел. Выяснить, какое число встречается раньше.

Как найти в массиве максимальное число?
как найти в массиве максимальное число?пример.

17.04.2012, 16:36217.04.2012, 19:18317.04.2012, 21:06418.04.2012, 07:01528.05.2013, 23:01628.05.2013, 23:04729.05.2013, 02:14829.05.2013, 12:389

Он абсолютно прав. При поиске минимума/максимума надо начальное значение выставлять соответственно максимально/минимально возможное. В Вашем случае:

29.05.2013, 13:081029.05.2013, 17:2911

29.05.2013, 17:3212

я думаю это и так было понятно 🙂

24.04.2014, 18:0613

Массив случайных чисел

-4 -3 11 3 4 4 -4 6 -1 9 -10 11
Максимальное значение массива 11
Минимальное значение массива -4

А минимальное -3. Иногда с максимумом ошибка, но всегда она есть. Как же правильно будет?

24.04.2014, 23:291425.04.2014, 18:1315

25.04.2014, 18:13

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Как найти число в большом массиве?
Здравствуйте. Есть массив на 1000000 элементов в котором все числа разные в диапазоне от 0 до 2^32.

Как в массиве найти число 100?
Помогите пожалуйста. очень-очень нужно. задачка такая: дан файл с данными о товарах на.

как найти наибольшее число в массиве чисел?
с помощью math.max я так понял нельзя?

Как в массиве из действительных чисел найти число кратное 5
Дан массив из действительных чисел и нужно найти в этой последовательности член кратный 5, вся.

6 алгоритмов поиска на Java: от простого к сложному

Поиск – распространённое действие, выполняемое в бизнес-приложениях. Под катом лежат реализации известных алгоритмов поиска на Java.

Программирование на Java – всегда интересный экспириенс. Но куда интереснее работать, применяя правильные для конкретных ситуаций алгоритмы.

Реализуем алгоритмы на Java и проанализируем производительность с помощью параметров временной и пространственной сложности.

Линейный поиск

Линейный или последовательный поиск – простейший алгоритм поиска. Он редко используется из-за своей неэффективности. По сути, это метод полного перебора, и он уступает другим алгоритмам.

У линейного поиска нет предварительных условий к состоянию структуры данных.

Объяснение

Алгоритм ищет элемент в заданной структуре данных, пока не достигнет конца структуры.

При нахождении элемента возвращается его позиция в структуре данных. Если элемент не найден, возвращаем -1 .

Реализация

Теперь посмотрим, как реализовать линейный поиск в Java:

Для проверки используем целочисленный массив:

Простой метод для вывода результата:

Временная сложность

Для получения позиции искомого элемента перебирается набор из N элементов. В худшем сценарии для этого алгоритма искомый элемент оказывается последним в массиве.

В этом случае потребуется N итераций для нахождения элемента.

Следовательно, временная сложность линейного поиска равна O(N).

Пространственная сложность

Этот поиск требует всего одну единицу памяти для хранения искомого элемента. Это не относится к размеру входного массива.

Следовательно, пространственная сложность линейного поиска равна O(1).

Применение

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

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

Двоичный поиск

Двоичный или логарифмический поиск часто используется из-за быстрого времени поиска.

Объяснение

Этот вид поиска использует подход «Разделяй и властвуй», требует предварительной сортировки набора данных.

Алгоритм делит входную коллекцию на равные половины, и с каждой итерацией сравнивает целевой элемент с элементом в середине. Поиск заканчивается при нахождении элемента. Иначе продолжаем искать элемент, разделяя и выбирая соответствующий раздел массива. Целевой элемент сравнивается со средним.

Вот почему важно иметь отсортированную коллекцию при использовании двоичного поиска.

Поиск заканчивается, когда firstIndex (указатель) достигает lastIndex (последнего элемента). Значит мы проверили весь массив Java и не нашли элемента.

Есть два способа реализации этого алгоритма: итеративный и рекурсивный.

Временная и пространственная сложности одинаковы для обоих способов в реализации на Java.

Реализация

Итеративный подход

Рекурсивный подход

Теперь посмотрим на рекурсивную реализацию:

Рекурсивный подход отличается вызовом самого метода при получении нового раздела. В итеративном подходе всякий раз, когда мы определяли новый раздел, мы изменяли первый и последний элементы, повторяя процесс в том же цикле.

Другое отличие – рекурсивные вызовы помещаются в стек и занимают одну единицу пространства за вызов.

Используем алгоритм следующим способом:

Временная сложность

Временная сложность алгоритма двоичного поиска равна O(log (N)) из-за деления массива пополам. Она превосходит O(N) линейного алгоритма.

Пространственная сложность

Одна единица пространства требуется для хранения искомого элемента. Следовательно, пространственная сложность равна O(1).

Рекурсивный двоичный поиск хранит вызов метода в стеке. В худшем случае пространственная сложность потребует O(log (N)).

Применение

Этот алгоритм используется в большинстве библиотек и используется с отсортированными структурами данных.

Двоичный поиск реализован в методе Arrays.binarySearch Java API.

Алгоритм Кнута – Морриса – Пратта

Алгоритм КМП осуществляет поиск текста по заданному шаблону. Он разработан Дональдом Кнутом, Воном Праттом и Джеймсом Моррисом: отсюда и название.

Объяснение

В этом поиске сначала компилируется заданный шаблон. Компилируя шаблон, мы пытаемся найти префикс и суффикс строки шаблона. Это поможет в случае несоответствия – не придётся искать следующее совпадение с начального индекса.

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

КМП работает быстрее алгоритма перебора благодаря пропускам.

Реализация

Итак, пишем метод compilePatternArray() , который позже будет использоваться алгоритмом поиска КМП:

Скомпилированный массив Java можно рассматривать как массив, хранящий шаблон символов. Цель – найти префикс и суффикс в шаблоне. Зная эти элементы, можно избежать сравнения с начала текста после несоответствия и приступать к сравнению следующего символа.

Скомпилированный массив сохраняет позицию предыдущего местонахождения текущего символа в массив шаблонов.

Давайте реализуем сам алгоритм:

Здесь мы последовательно сравниваем символы в шаблоне и текстовом массиве. Мы продолжаем двигаться вперёд, пока не получим совпадение. Достижение конца массива при сопоставлении означает нахождение шаблона в тексте.

Но! Есть один момент.

Если обнаружено несоответствие при сравнении двух массивов, индекс символьного массива перемещается в значение compiledPatternArray() . Затем мы переходим к следующему символу в текстовом массиве. КМП превосходит метод грубой силы однократным сравнением текстовых символов при несоответствии.

В текстовом шаблоне AAABAAA наблюдается и кодируется в массив шаблонов следующий шаблон:

Шаблон A (Одиночная A) повторяется в 1 и 4 индексах.
Паттерн AA (Двойная A) повторяется во 2 и 5 индексах.
Шаблон AAA (Тройная A) повторяется в индексе 6.

В подтверждение наших расчётов:

Описанный выше шаблон ясно показан в скомпилированном массиве.

С помощью этого массива КМП ищет заданный шаблон в тексте, не возвращаясь в начало текстового массива.

Временная сложность

Для поиска шаблона алгоритму нужно сравнить все элементы в заданном тексте. Необходимое для этого время составляет O(N). Для составления строки шаблона нам нужно проверить каждый символ в шаблоне – это еще одна итерация O(M).

O (M + N) – общее время алгоритма.

Пространственная сложность

O(M) пространства необходимо для хранения скомпилированного шаблона для заданного шаблона размера M.

Применение

Этот алгоритм используется в текстовых инструментах для поиска шаблонов в текстовых файлах.

Поиск прыжками

От двоичного поиска этот алгоритм отличает движение исключительно вперёд. Имейте в виду, что такой поиск требует отсортированной коллекции.

Мы прыгаем вперёд на интервал sqrt(arraylength) , пока не достигнем элемента большего, чем текущий элемент или конца массива. При каждом прыжке записывается предыдущий шаг.

Прыжки прекращаются, когда найден элемент больше искомого. Затем запускаем линейный поиск между предыдущим и текущим шагами.

Это уменьшает поле поиска и делает линейный поиск жизнеспособным вариантом.

Реализация

Мы начинаем с jumpstep размером с корень квадратный от длины массива и продолжаем прыгать вперёд с тем же размером, пока не найдём элемент, который будет таким же или больше искомого элемента.

Сначала проверяется элемент integers[jumpStep] , затем integers[2jumpStep] , integers[3jumpStep] и так далее. Проверенный элемент сохраняется в переменной previousStep .

Когда найдено значение, при котором integers[previousStep] , производится линейный поиск между integers[previousStep] и integers[jumpStep] или элементом большим, чем elementToSearch .

Вот так используется алгоритм:

Временная сложность

Поскольку в каждой итерации мы перепрыгиваем на шаг, равный sqrt(arraylength) , временная сложность этого поиска составляет O(sqrt (N)).

Пространственная сложность

Искомый элемент занимает одну единицу пространства, поэтому пространственная сложность алгоритма составляет O(1).

Применение

Этот поиск используется поверх бинарного поиска, когда прыжки в обратную сторону затратны.

С ограничением сталкиваются при работе с вращающейся средой. Когда при легком поиске по направлению вперёд многократные прыжки в разных направлениях становятся затратными.

Интерполяционный поиск

Интерполяционный поиск используется для поиска элементов в отсортированном массиве. Он полезен для равномерно распределенных в структуре данных.

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

Для поиска элементов в массиве алгоритм использует формулы интерполяции. Эффективнее применять эти формула для больших массивов. В противном случае алгоритм работает как линейный поиск.

Реализация

Используем алгоритм так:

Смотрите, как работают формулы интерполяции, чтобы найти 6 :

Теперь давайте применим эти значения к формулам для оценки индекса элемента поиска:

index=0+(7−0)/(8−1)∗(6−1)=5

Элемент integers[5] равен 6 — это элемент, который мы искали. Индекс для элемента рассчитывается за один шаг из-за равномерной распределенности данных.

Временная сложность

В лучшем случае временная сложность такого алгоритма – O(log log N). При неравномерном распределении элементов сложность сопоставима с временной сложностью линейного алгоритма, которая = O(N).

Пространственная сложность

Алгоритм требует одну единицу пространства для хранения элемента для поиска. Его пространственная сложность = O(1).

Применение

Алгоритм полезно применять для равномерно распределенных данных вроде телефонной книги.

Экспоненциальный поиск

Экспоненциальный поиск используется для поиска элементов путём перехода в экспоненциальные позиции, то есть во вторую степень.

В этом поиске мы пытаемся найти сравнительно меньший диапазон и применяем на нем двоичный алгоритм для поиска элемента.

Для работы алгоритма коллекция должна быть отсортирована.

Реализация

Применяем алгоритм Java:

Мы пытаемся найти элемент больше искомого. Зачем? Для минимизации диапазона поиска. Увеличиваем диапазон, умножая его на 2, и снова проверяем, достигли ли мы элемента больше искомого или конца массива. При нахождении элемента мы выходим из цикла. Затем выполняем бинарный поиск с startIndex в качестве range/2 и lastIndex в качестве range .

В нашем случае значение диапазона достигается в элементе 8, а элемент в integers[8] равен 95. Таким образом, диапазон, в котором выполняется бинарный поиск:

При этом вызываем бинарный поиск:

Здесь важно отметить, что можно ускорить умножение на 2, используя оператор левого сдвига range вместо * .

Временная сложность

В худшем случае временная сложность этого поиска составит O(log (N)).

Пространственная сложность

Итеративный алгоритм двоичного поиска требует O(1) места для хранения искомого элемента.

Для рекурсивного двоичного поиска пространственная сложность становится равной O(log (N)).

Применение

Экспоненциальный поиск используется с большими массивами, когда бинарный поиск затратен. Экспоненциальный поиск разделяет данные на более доступные для поиска разделы.

Заключение

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

В этой статье мы рассмотрели работу алгоритмов поиска Java и случаи их применения.

0 0 голоса

Рейтинг статьи