Java массив поиск элементов

Поиск элемента в массиве

Достаточно частая задача — это поиск элемента в массиве. Допустим у нас есть массив 1,5,8,10,16,20. 100 и нам нужно найти позицию элемента 10 в нем. Или вообще выяснить есть ли такой элемент в массиве.

Существуют следующие алгоритмы решающие эту задачу —

• Линейный поиск — О(n)
• Двоичный поиск — O(log (N))
• Поиск прыжками — O(sqrt (N))
• Интерполяционный поиск — O(log log N)
• Экспоненциальный поиск — O(log (N))

Рассмотрим некоторые из них.

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

Самый простой, но и самый долгий алгоритм. Перебираем элементы массива и сравниваем с elementToSearch, который мы должны найти.

 public static int linearSearch(int[] array, int elementToSearch) < for (int i = 0; i < array.length; i++) < if (array[i] == elementToSearch) < return i; >> return -1; >

2. Двоичный поиск, итеративный подход

Для использования алгоритма, массив должен быть отсортирован. Идея метода состоит в том, что мы делим массив пополам, берем «средний элемент» с индексом middleIndex, и сравниваем с искомым. Если они равны, мы заканчиваем поиск. Если искомый элемент меньше «среднего элемента» мы отбрасываем правую часть массива, иначе — левую. После чего повторяем эти операции снова и снова, пока искомый элемент не будет найден, или пока новый отрезок не станет пустым. Если элемент не нашелся возвращаем значение -1.

public static int binarySearch(int[] array, int elementToSearch) < int firstIndex = 0; int lastIndex = array.length - 1; // условие прекращения (элемент не представлен) while (firstIndex // если средний элемент меньше // направляем наш индекс в middle+1, убирая первую часть из рассмотрения else if (array[middleIndex] < elementToSearch) < firstIndex = middleIndex + 1; >// если средний элемент больше // направляем наш индекс в middle-1, убирая вторую часть из рассмотрения else if (array[middleIndex] > elementToSearch) < lastIndex = middleIndex - 1; >> return -1; >

3. Двоичный поиск, рекурсивный подход

 public static int recursiveBinarySearch(int[] array, int firstElement, int lastElement, int elementToSearch) < // условие прекращения if (lastElement >= firstElement) < int middle = (lastElement + firstElement) / 2; // если средний элемент - целевой элемент, вернуть его индекс if (array[middle] == elementToSearch) < return middle; >// если средний элемент больше целевого // вызываем метод рекурсивно по суженным данным if (array[middle] > elementToSearch) < return recursiveBinarySearch(array, firstElement, middle - 1, elementToSearch); >// также, вызываем метод рекурсивно по суженным данным return recursiveBinarySearch(array, middle + 1, lastElement, elementToSearch); > return -1; >

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

 public static int jumpSearch(int[] array, int elementToSearch) < int arrayLength = array.length; int jumpStep = (int) Math.sqrt(array.length); int previousStep = 0; while (array[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) < previousStep = jumpStep; jumpStep += (int) (Math.sqrt(arrayLength)); if (previousStep >= arrayLength) < return -1; >> while (array[previousStep] < elementToSearch) < previousStep++; if (previousStep == Math.min(jumpStep, arrayLength)) < return -1; >> if (array[previousStep] == elementToSearch) < return previousStep; >return -1; >

Источник

Кофе-брейк #221. Три способа, как найти элемент в массиве Java. Что такое Java Thread Local и как его использовать

Источник: Asyncq Эта публикация поможет вам лучше узнать, какие существуют способы поиска элемента в массиве в Java. Поиск определенного элемента в наборе значений — очень распространенная и часто используемая операция в разработке программного обеспечения. Существуют разные подходы к решению этой проблемы, от простых до оптимизированных. Давайте их рассмотрим.

Вводные данные

Вводный массив содержит примитивные данные идентификаторов, и нам нужно узнать, содержится ли в нем id->3.

Способ 1 (простой)

1. Посещаем все элементы массива, поочередно по одному элементу.
2. Дополнительно отслеживаем состояние целевого элемента, если он существует в массиве.
3. Как только мы находим этот элемент, то переключаем статус с false на true .
4. После завершения цикла возвращаем флаг состояния.

 boolean valExist = false; for (int id : ids) < if (inputId == id) < valExist = true; >> return valExist; 

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

 boolean valExist = false; for (int id : ids) < if (inputId == id) < valExist = true; break; >> return valExist; 

Можно сделать код еще более кратким, используя return . Мы можем вернуть true , как только увидим искомый элемент, в противном случае возвращаем false , как только цикл завершится. И нам не нужно создавать и поддерживать переменную состояния.

 for (int id : ids) < if (inputId == id) < return true; >> return false; 

Способ 2

1. Мы можем использовать ArrayList , содержащий метод, который по умолчанию ищет целевой элемент в списке.
2. Поскольку этот метод предоставляется List , нам нужно преобразовать наш примитивный массив в список.
3. Мы можем использовать одну лямбда-строку, которая преобразует примитив в тип объекта и создает из него список (list).

 return Arrays.asList(Arrays.stream(ids).boxed().toArray()) .contains(inputId); 

 return Arrays.stream(ids) .anyMatch(id -> inputId); 

Способ 3 (оптимизированный)

1. Если с памятью нет проблем и мы хотим оптимизировать вычисления, то одна из вещей, которые мы можем здесь сделать, — это создать набор из вводного массива.
2. Мы снова можем использовать код функционального стиля для преобразования примитивного массива в Set .
3. Теперь, когда у нас есть Set , мы можем искать элемент в течение постоянного время.

 et idsSet = Arrays.stream(ids).boxed().collect(Collectors.toSet()); return idsSet.contains(inputId); 

Бонус

Поиск одного элемента можно считать обычной операцией, но более распространенным все же является поиск нескольких элементов в массиве. В данном случае, если мы не используем Set , у нас будет два цикла, а временная сложность увеличится до умножения длины двух коллекций. Ниже приведен пример, в котором мы преобразуем один из массивов как набор (set), а затем перебираем другой массив и выполняем поиск в операции набора. Делая это, мы увеличиваем память и при этом экономим на вычислениях.

 int[] targetIds = < 1, 3, 6, 88, 999, 34, 44, 55>; int[] ids = < 1,2,13,14,15,3,10,11,12,4,5,6,7,8,9 >; Set idsSet = Arrays.stream(ids).boxed().collect(Collectors.toSet()); return Arrays.stream(targetIds) .boxed() .filter(id -> !idsSet.contains(id)) .mapToInt(a -> a) .toArray(); 

Что такое Java Thread Local и как его использовать

Источник: Medium В данной статье мы рассмотрим Java Thread Local и способы его эффективного использования в ваших Java-приложениях. Java Thread Local — это мощная функция, которая позволяет разработчикам создавать переменные только для определенного потока. Это означает, что у каждого потока может быть своя копия переменной, и изменения, внесенные в переменную в одном потоке, не повлияют на ее значение в другом потоке.

Что такое Thread Local

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

Как работает Thread Local в Java

Чтобы использовать Thread Local в вашем Java-приложении, сначала нужно создать экземпляр класса Thread Local . Это можно сделать, вызвав конструктор ThreadLocal , который и создаст новый экземпляр этого класса. Далее, создав объект Thread Local , вы можете использовать его для хранения и извлечения данных, специфичных для каждого потока. Вот пример того, как использовать Thread Local в вашем Java-приложении:

 public class MyThreadLocalClass < private static final ThreadLocalthreadLocal = new ThreadLocal<>(); public static void set(String value) < threadLocal.set(value); >public static String get() < return threadLocal.get(); >> 

В этом примере мы создали объект Thread Local по имени threadLocal типа String . Мы также создали два метода: set() и get() , которые позволяют нам сохранять и извлекать значение переменной Thread Local . Чтобы сохранить значение в переменной Thread Local , мы просто вызываем метод set() и передаем значение, которое хотим сохранить. Например, мы можем вызвать MyThreadLocalClass.set(«Hello, World!») для сохранения строки “Hello, World!” в переменной Thread Local . Чтобы получить значение переменной Thread Local , мы просто вызываем метод get() . Например, мы можем вызвать String value = MyThreadLocalClass.get() для получения значения переменной Thread Local .

Рекомендации по работе с Thread Local

1. Используйте Thread Local только при необходимости: лишь для данных, относящихся к потоку. Если данные не относятся к конкретному потоку, они должны храниться другим способом.
2. Избегайте чрезмерного использования памяти: Thread Local может потреблять значительный объем памяти, если не использовать его осторожно. Обязательно очищайте переменные Thread Local , когда они больше не нужны, чтобы избежать чрезмерного использования памяти.
3. Используйте Thread Local с осторожностью в многопоточных средах: важно понимать потенциальные риски и ограничения. Обязательно тщательно протестируйте свой код, чтобы убедиться, что Thread Local работает должным образом в вашей конкретной среде.

Заключение

Java Thread Local — отличный инструмент, позволяющий разработчикам создавать переменные только для определенного потока. Используя Thread Local , вы можете хранить данные, относящиеся к потоку, например информацию об аутентификации пользователя, подключения к базе данных или другую информацию, относящуюся к потоку. Хотя Thread Local может быть мощным инструментом, важно использовать его правильно, чтобы избежать потенциальных проблем. Следуя рекомендациям и тестируя свой код, вы сможете эффективно его использовать для повышения производительности и надежности ваших Java-приложений.

Источник

Кофе-брейк #156. Как использовать метод Arrays.binarySearch() в Java

Источник: FreeCodeCamp Благодаря этой статье вы узнаете, как использовать метод Arrays.binarySearch() в языке Java.

Что такое Arrays.binarySearch() в языке Java?

• Этот метод ищет в указанном массиве байтов указанное значение, используя алгоритм двоичного поиска.
• Массив должен быть отсортирован (по методу sort(byte[]) ) перед выполнением вызова. Если он не отсортирован, результаты не будут определены.
• Если массив содержит несколько элементов с указанным значением, нет гарантии, какой из них будет найден.

 import java.util.Arrays; public class Main < public static void main(String[] args) < char vowels[] = ; char key = 'i'; int foundItemIndex = Arrays.binarySearch(vowels, key); System.out.println("The given vowel is at index: " + foundItemIndex); > > 

Метод Arrays.binarySearch() принимает массив, который вы хотите найти, в качестве первого аргумента, и ключ, который вы ищете, в качестве второго аргумента. Результатом указанной выше программы будет:

Помните, что метод возвращает индекс найденного элемента, а не сам элемент. Таким образом вы можете сохранить индекс в виде целого числа, подобного тому, который используется в этом примере. По умолчанию метод использует первый индекс массива в качестве начальной точки поиска и длину массива в качестве конечной точки поиска. В этом случае начальный индекс равен 0, а конечный индекс — 6. Вместо того, чтобы использовать начальный и конечный индексы по умолчанию, вы можете определить их самостоятельно. Например, если вы хотите выполнить поиск от индекса 2 к индексу 4, то это можно сделать так:

 import java.util.Arrays; public class Main < public static void main(String[] args) < char vowels[] = ; char key = 'i'; int startIndex = 2; int endIndex = 4; int foundItemIndex = Arrays.binarySearch(vowels, startIndex, endIndex, key); System.out.println("The given vowel is at index: " + foundItemIndex); > > 

В этом случае метод Arrays.binarySearch() принимает массив, который вы хотите найти, в качестве первого аргумента, начальный индекс — в качестве второго аргумента, конечный индекс — в качестве третьего и ключ — в качестве четвертого. Пока вы сохраняете конечный индекс в пределах длины массива, метод должен работать нормально. Но если вы его превысите, то получите исключение Array index out of range . Всё довольно просто, верно? Метод возвращает индекс элемента, если он найден. Но что произойдет, если он не найдет данный элемент?

Что происходит, когда Arrays.binarySearch() не находит данный элемент?

• Метод находит индекс ключа в результатах поиска, если он содержится в массиве в пределах указанного диапазона; иначе получаем (-(insertion point) — 1) .
• Точка вставки определяется как точка, в которой ключ будет вставлен в массив: индекс первого элемента в диапазоне больше, чем ключ, или toIndex (конечный индекс), если все элементы в диапазоне меньше указанного ключа.
• Обратите внимание, что возвращаемое значение будет больше или равно 0 только тогда, когда ключ найден.

 package arrays; import java.util.Arrays; public class Main < public static void main(String[] args) < int numbers[] = ; System.out.println(Arrays.binarySearch(numbers, 0)); // -1 > > 

Давайте снова предположим, что у нас есть массив [5, 6, 7, 8, 9, 10] и ключ поиска 12 , которого явно нет в массиве. В этом случае ключ поиска больше, чем все элементы массива. Здесь insertion point будет таким:

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

 import java.util.Arrays; public class Main < public static void main(String[] args) < int numbers[] = ; System.out.println(Arrays.binarySearch(numbers, 12)); // -7 > > 

 import java.util.Arrays; public class Main < public static void main(String[] args) < int numbers[] = ; int startIndex = 1; int endIndex = 3; System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 5)); // -2 System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 10)); // -4 > > 

Попробуйте рассчитать значения самостоятельно. Вы также можете использовать метод Arrays.binarySearch() с такими символами:

 import java.util.Arrays; public class Main < public static void main(String[] args) < char vowels[] = ; char key = 'i'; int startIndex = 2; int endIndex = 4; System.out.println(Arrays.binarySearch(vowels, startIndex, endIndex, key)); > > 

Те же принципы применяются и в том случае, когда заданный ключ поиска не найден. Но при сравнении между символом в массиве и заданным поисковым ключом будет использоваться ASCII-код соответствующего символа. То есть A (65) будет меньше, чем a (97) . Учтите это при перекрестной проверке выходных данных вашей программы.

Источник