Линейный поиск: пример Python, C++

Что такое Сеarchiнг алгоритм?

А сеarchiАлгоритм ng предназначен для поиска элемента или объекта из коллекции элементов или объектов с заданной структурой данных. Например, найдите минимальную высоту в заданном списке высот или найдите самую высокую отметку в списке или массиве чисел. Мало популярных наборовarchiАлгоритмы ng включают «Линейный поиск», «Двоичный поиск», «Поиск с переходом», «Поиск Фибоначчи» и т. д.

Что такое линейный поиск?

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

Что делает функция линейного поиска?

Массив целых чисел задается как «Числа», а переменная «item» содержит целое число для поиска.

Теперь алгоритм линейного поиска может обеспечить следующее:wing вывод:

  • «-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

сplexАнализ эффективности алгоритма линейного поиска

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

Три типа времениplexэто:

  • Worst Case Scenario
  • Сценарий лучшего случая
  • Средний сценарий

Время Комplexэффективность линейного поиска в наихудшем сценарии:

Допустим, нам нужно выполнить линейный поиск в массиве размером «n». Мы можем найти элемент поиска между индексами от 0 до n-1. В худшем случае алгоритм попытается сопоставить все элементы массива с элементом поиска.

В этом случае худший вариант ком.plexность будет O(n). Здесь «О»-большая буква «О» означает com.plexфункция.

Время Комplexэффективность линейного поиска в наилучшем сценарии:

Допустим, мы готовыarching для элемента, который находится в первой позиции массива. В этом сценарии алгоритм линейного поиска не будет искать все n элементов массива. Итак, комplexэффективность будет O(1). Это означает постоянное время.

Время Комplexность линейного поиска в среднестатистическом сценарии:

Когда элемент находится по среднему индексу массива, можно сказать, что средний случай complexСкорость линейного поиска равна O(N), где N означает длину массива.

Космическая связьplexэффективность алгоритма линейного поиска

Космос комplexСкорость линейного поиска всегда равна O(N), поскольку нам не нужно хранить или использовать какие-либо временные переменные в функции линейного поиска.

Как улучшить алгоритм линейного поиска

Поиск можно выполнять несколько раз на протяжении жизненного цикла программы. Также возможно, что мы запускаем алгоритм линейного поиска и видимarching для любого конкретного ключа несколько раз. Мы можем использовать «Алгоритм двоичного поиска», если массив является отсортированным.

Предположим, что массив состоит из 10 тысяч чисел, а целевой элемент находится по 5000-му индексу. Итак, алгоритм попытается сравнить 5000 элементов. Теперь сравнения — это задача, нагружающая процессор. Чтобы оптимизировать алгоритм линейного поиска, у нас есть два варианта.

  • перестановка
  • На передний план

Транспозиция:

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

Данные[] = {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).

Переместиться на передний план в линейном поиске

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

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

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