Java алгоритм линейный поиск

Структура данных и алгоритмы: Линейный поиск

Что такое Поиск? В информатике поиск – это “процесс поиска элемента с помощью… Помечено структурой данных, алгоритмами, java, линейным поиском.

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

Но зачем нам нужен Поиск?

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

Некоторыми примерами алгоритмов поиска являются Линейный поиск, Двоичный поиск, Интерполяционный поиск и т.д. Здесь мы обсудим Линейный поиск.

Линейный поиск – это простой алгоритм поиска, который последовательно проверяет каждый элемент в коллекции. Если совпадение найдено, товар возвращается, в противном случае поиск продолжается до конца коллекции. Предположим, что вам дан массив, в котором порядок элементов неизвестен. В этом случае вам придется просмотреть каждый элемент массива, чтобы найти элемент с указанным свойством.

Алгоритм может быть написан следующим образом:

• Дан массив Arr и элемент , который нужно найти данные .
• Проверьте первый элемент. Если оно равно данным, верните позицию первого элемента. В противном случае проверьте наличие следующего элемента.
• Проверяйте до тех пор, пока не будет сравнен последний элемент.
• Если данные не найдены в массиве, верните значение -1. Этот тип линейного поиска называется неупорядоченным линейным поиском

public int unorderedLinearSearch(int[] Arr, int data) < for(int i=0; i="">

Временная сложность: O(n), в худшем случае мы сканируем весь массив. Сложность пространства: O(1)

Теперь, если массив Arr отсортирован, т.е. мы знаем порядок элементов, мы можем выполнить поиск следующим образом:

Этот случай называется упорядоченным линейным поиском

public int orderedLinearSearch(int[] Arr, int data) < for(int i=0; idata) return -1; > return -1; > 

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

• в последней позиции в массиве от O(n) до O(1) или,
• отсутствует в массиве, от O(n) до (n/2) путем проверки элементов слева и справа.

public int optimiseLinearSearch(int[] Arr, int data) < int left = 0; int length = Arr.length; int right = length - 1; int position = -1; for (left = 0; left if (Arr[right] == search_Element) < position = right; System.out.println(position); break; >left++; right--; > if (position == -1) System.out.println("data not found"); > >

Поздравляю! Теперь вы знаете, что такое алгоритмы поиска и как реализован алгоритм линейного поиска.

В следующем блоге мы рассмотрим еще несколько концепций структур данных и алгоритмов!

Читайте ещё по теме:

Источник

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

Достаточно частая задача — это поиск элемента в массиве. Допустим у нас есть массив 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; >

Источник

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

Когда вы открываете веб-браузер, ищете страничку, информацию, друзей в соцсетях, вы совершаете поиск, точно так же, как при попытке найти нужную пару обуви в магазине.

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

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

Пример. пусть у нас есть список чисел:

И нам нужно найти 0. Мы его видим сразу, но компьютерная программа так не работает. Она начинает с начала списка и видит число 2. Затем проверяет, 2=0? Это не так, поэтому она продолжает работу и переходит ко второму символу. Там её тоже ждет неудача, и только на третьей позиции алгоритм находит нужное число.

Псевдокод линейного поиска:

linearSearch(key, array[]): for(i = 0; i < length(array); i++): if(array[i] == key): return i return -1

Функция linearSearch получает на вход два аргумента — ключ key и массив array[] .Ключ — искомое значение, в предыдущем примере key = 0 . Массив — список чисел, которые мы будем просматривать. Если мы ничего не нашли, функция вернет -1 (позицию, которой в массиве нет). Если же линейный поиск найдет нужный элемент, то функция вернет позицию, на которой находится искомый элемент в массиве.

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

Если вам нужно найти число 198 в массиве из 200 чисел, отсортированных по порядку, цикл for пройдет 198 шагов.

Вы, вероятно, уже догадались, какой способ работает лучше для отсортированного массива?

Источник