Введение в алгоритм линейного поиска: введение и функции [с примерами]

Что такое поиск?

Поиск — это процесс нахождения заданного элемента в списке элементов. Это помогает в поиске конкретной записи. Следовательно, это метод определения места данного предмета. Успех процесса поиска зависит от того, был ли идентифицирован элемент, подлежащий поиску, или нет.

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

1. Линейный поиск или последовательный поиск
2. Бинарный поиск

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

Алгоритмы линейного поиска — это тип алгоритма последовательного поиска данных. Этот алгоритм находит заданный элемент со сложностью O(n). Он применяется к коллекции элементов. Каждый элемент данных ищется последовательно и возвращается, если он соответствует искомому элементу. Если совпадений не найдено, поиск продолжается до конца собранных данных. По сути, это метод изучения каждого элемента при обходе списка. Алгоритм поиска может применяться как к отсортированным, так и к несортированным данным. Практически линейный поиск редко используется из-за более быстрых вариантов поиска, предоставляемых другими алгоритмами поиска, такими как алгоритмы бинарного поиска и хеш-таблицы.

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

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

Особенности алгоритмов линейного поиска

1. Обычно он применяется к небольшому списку несортированных или неупорядоченных данных.
2. Время линейно зависит от количества элементов, поэтому имеет временную сложность, если O (n).
3. Реализация очень проста.

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

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

• алгоритм Seqnl_Search(список, элемент)
• Предварительно: список != ;
• Сообщение: вернуть индекс элемента, если он найден, иначе: 1
• индекс <- фи
• while index < list.Cnt и list[index] != item //cnt: переменная-счетчик
• индекс <- индекс + 1
• конец, пока
• если индекс < list.Cnt и список [индекс] = элемент
• возвращаемый индекс
• конец, если
• возврат: 1
• конец Seqnl_Search

Пример линейного поиска

Задача: задан массив arr[] из n элементов. Напишите функцию для поиска заданного элемента x в массиве arr[].

Рис. 1. Пример кода, показывающий реализацию алгоритма линейного поиска.

Источник

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

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

Рис. 2. Пример кода, показывающего алгоритм линейного поиска на языке Python.

Источник

Вывод: элемент присутствует в индексе 3

2. Линейный поиск в C

Рисунок 3: Пример кода, показывающего алгоритм линейного поиска на языке C

Источник

Вывод : элемент присутствует в индексе 3

3. Линейный поиск в структуре данных

Псевдокод для задачи линейного поиска в структуре данных

Рисунок 4: Псевдокод для алгоритма линейного поиска

Источник

Бинарный поиск

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

Алгоритм бинарного поиска включает в себя следующие шаги

• Сравнение искомого элемента с элементом из середины списка или массива.
• Если элемент совпадает с элементом из списка, он возвращает индекс среднего элемента.
• Если совпадение не возвращается, проверяется, больше или меньше элемент, чем элемент в середине.
• Для элемента большего значения, чем средний элемент, поиск выполняется в правой части массива.
• Точно так же, если элемент меньше по значению, чем средний элемент, поиск продолжается в левой части списка.

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

Особенности бинарного поиска

• Алгоритм бинарного поиска полезен для поиска большого количества элементов в массиве.
• Алгоритм бинарного поиска имеет временную сложность O(logn).
• Реализация алгоритма бинарного поиска проста.

Алгоритм бинарного поиска

• Алгоритм Binary_Search(список, элемент)
• Установите L на 0 и R на n: 1
• если L > R, то Binary_Search завершается как неудачный
• еще
• Установите m (положение в среднем элементе) на пол (L + R) / 2
• если Am < T, установите L равным m + 1 и перейдите к шагу 3.
• если Am > T, установите R равным m: 1 и перейдите к шагу 3.
• Теперь Ам = Т,
• поиск выполнен; возвращение (м)

Заключение

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

Если вы заинтересованы в науке о данных, вы должны ознакомиться с программой Executive PG IIIT-B и upGrad по науке о данных, которая была тщательно разработана для работающих профессионалов и предлагает многочисленные тематические исследования, практические семинары, индивидуальное наставничество и гораздо более.