Линейный поиск: Python, C++ Пример
Что такое алгоритм поиска?
Алгоритм поиска предназначен для поиска элемента или объекта из коллекции элементов или объектов с заданной структурой данных. Например, найдите минимальную высоту в заданном списке высот или найдите самую высокую отметку в списке или массиве чисел. К числу популярных алгоритмов поиска относятся «Линейный поиск», «Двоичный поиск», «Поиск с переходом», «Поиск Фибоначчи» и т. д.
Что такое линейный поиск?
Линейный поиск — один из простейших алгоритмов поиска. В заданном списке или массиве он ищет данный элемент один за другим. Линейный поиск перебирает весь список и проверяет, равен ли какой-либо конкретный элемент элементу поиска. Его также называют последовательный поиск.
Что делает функция линейного поиска?
Массив целых чисел задается как «Numbers», а переменная «item» содержит целое число для поиска.
Теперь алгоритм линейного поиска может обеспечить следующий результат:
- «-1»; это означает, что данный элемент не найден в массиве
- Любое число от 0 до n-1; означает, что элемент поиска найден, и возвращает индекс элемента в массиве. Здесь «n» представляет размер массива.
Как работает линейный поиск?
Допустим, массив, содержащий целые числа. Задача — найти заданное число в массиве.
- Если число находится в массиве, нам нужно вернуть индекс этого числа.
- Если данное число не найдено, оно вернет -1.
На блок-схеме «Данные» — это целочисленный массив, «N» — размер массива, а «элемент» — это число, которое мы хотим найти в массиве.
Блок-схема алгоритма линейного поиска:
Вот этапы блок-схемы:
Шаг 1) Прочитайте элемент поиска, «элемент».
Шаг 2) Инициировать i=0 и индекс=-1
Шаг 3) Если я
Шаг 4) Если Data[i] равно «item», перейдите к шагу 5. В противном случае перейдите к шагу 6.
Шаг 5) Индекс = i (поскольку элемент находится по индексу i). Перейдите к шагу 8.
Шаг 6) я = я +1.
Шаг 7) Переходите к шагу 3.
Шаг 8) Стоп.
Для простоты мы приводим пример с массивом целых чисел. Линейный поиск также применим в строке, массиве объектов или структуре.
Псевдокод для алгоритма последовательного поиска
function linearSearch: in →Data[], item foundAt = -1 for i in (0 to data.length): if data[i] equals item // item is found in the array // returning the index return i // item not found in the array // -1 means no item found, as negative index is not valid return -1
C++ Пример кода: линейный поиск
#include < bits / stdc++.h > using namespace std; int linearSearch(int * arr, int item, int n) { int idx = -1; for (int i = 0; i < n; i++) { if (arr[i] == item) { idx = i; break; } } return idx; } int main() { int array[] = { 1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10 }; int n = sizeof(array) / sizeof(arr[0]); int item; cout << "Enter a number to search: "; cin >> item; int idx = linearSearch(arr, item, n); if (idx >= 0) { cout << item << " is found at index " << idx << endl; } else { cout << "Could not find " << item << " in the array" << endl; } }
Вывод:
Enter a number to search: -10 -10 is found at index 14
Python Пример кода: линейный поиск
def linearSearch(data, item): for i in range(len(data)): if data[i] == item: return i return -1 data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10] item = int(input("Enter a number to search: ")) idx = linearSearch(data, item) if idx >= 0: print("{} is found at index {}".format(item, idx)) else : print("{} was not found".format(item))
Вывод:
Enter a number to search: -10 -10 is found at index 14
Анализ сложности алгоритма линейного поиска
Как правило, временная сложность означает количество процессорного времени, необходимое для выполнения определенной задачи. В алгоритме линейного поиска задача состоит в том, чтобы найти ключ поиска по элементу массива.
Три типа временных сложностей:
- Worst Case Scenario
- лучший сценарий случая
- Средний сценарий
Временная сложность линейного поиска в наихудшем сценарии:
Допустим, нам нужно выполнить линейный поиск в массиве размером «n». Мы можем найти элемент поиска между индексами от 0 до n-1. В худшем случае алгоритм попытается сопоставить все элементы массива с элементом поиска.
В этом случае наихудшая сложность будет равна O(n). Здесь «O»-большая запись O означает функцию сложности.
Временная сложность линейного поиска в лучшем случае:
Допустим, мы ищем элемент, который находится в первой позиции массива. В этом сценарии алгоритм линейного поиска не будет искать все n элементов массива. Таким образом, сложность будет O (1). Это означает постоянное время.
Временная сложность линейного поиска в среднем случае:
Когда элемент найден по среднему индексу массива, можно сказать, что средняя сложность линейного поиска равна O (N), где N означает длину массива.
Пространственная сложность алгоритма линейного поиска
Пространственная сложность для линейного поиска всегда равна O(N), поскольку нам не нужно хранить или использовать какие-либо временные переменные в функции линейного поиска.
Как улучшить алгоритм линейного поиска
Поиск можно выполнять несколько раз на протяжении жизненного цикла программы. Также возможно, что мы запускаем алгоритм линейного поиска и ищем какой-то конкретный ключ несколько раз. Мы можем использовать «Алгоритм двоичного поиска», если массив является отсортированным.
Предположим, что массив состоит из 10 тысяч чисел, а целевой элемент находится по 5000-му индексу. Итак, алгоритм попытается сравнить 5000 элементов. Теперь сравнения — это задача, нагружающая процессор. Чтобы оптимизировать алгоритм линейного поиска, у нас есть два варианта.
- перестановка
- На передний план
Транспозиция:
В этом методе мы заменим элемент поиска на предыдущий элемент массива. Например, предположим, что у вас есть массив, подобный следующему:
Данные[] = {1,5,9,8,7,3,4,11}
Теперь мы хотим найти 4. Шаги транспонирования:
Шаг 1) «4» находится под индексом 6. Потребовалось шесть сравнений.
Шаг 2) Поменяйте местами данные[6] и данные[5]. Тогда массив данных будет иметь вид:
Данные[] = {1,5,9,8,7,4,3,11}
Шаг 3) Найдите 4 еще раз. Нашел по индексу 5. На этот раз потребовалось пять сравнений.
Шаг 4) Поменяйте местами данные [5] и данные[4]. Тогда массив данных будет выглядеть так:
Данные [] = {1,5,9,8,4,7,3,11}
Теперь, если вы заметили, чем чаще выполняется поиск ключа, тем больше уменьшается индекс. Тем самым уменьшая количество сравнений.
Переместитесь вперед:
В этом методе мы меняем местами элемент поиска в 0-м индексе. Потому что, если его искать еще раз, мы сможем найти его за время O(1).
Применение алгоритма линейного поиска
Вот несколько приложений линейного поиска, которые мы можем использовать.
- Для массивов небольшого размера или всего нескольких элементов в списке проще использовать линейный поиск.
- Метод линейного поиска может использоваться как в одиночном, так и в многомерные массивы или другие структуры данных.
- Как правило, линейный поиск прост и эффективен для поиска в «неупорядоченных» данных. Мы можем легко получить отдельные данные из заданного неупорядоченного списка.