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

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

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

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

Вы могли бы: