Линейный поиск: 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) Стоп.

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

Прозвище Code для алгоритма последовательного поиска

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

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 a negative index is not valid
    return -1

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

Вот полный 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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code Пример линейного поиска

Та же логика в 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) Поменяйте местами data[5] и data[4]. Тогда массив данных будет выглядеть так:

Данные[] = {1,5,9,8,4,7,3,11}

Обратите внимание, что чем чаще выполняется поиск по ключу, тем больше уменьшается размер индекса. Следовательно, уменьшается и количество сравнений.

Переместитесь вперед:

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

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

Вот несколько приложений линейного поиска, которые мы можем использовать.

• Для небольших массивов или списков, содержащих лишь несколько элементов, проще использовать линейный поиск.
• Метод линейного поиска может использоваться как в одиночном, так и в многомерные массивы или другие структуры данных.
• Как правило, линейный поиск прост и эффективен для поиска в «неупорядоченных» данных. Мы можем легко получить отдельные данные из заданного неупорядоченного списка.

Часто задаваемые вопросы (FAQ)