Question

Написать функцию C ++ или Python, реализующую алгоритм линейного поиска для элемента массива, с барьером. Описать алгоритм

Answer 1

def LinearSearch(lys, element): #lys — массив, element — число, которое в дальнейшем должно найтись в массиве

   for i in range (len(lys)): #i — индексная переменная массива lys, цикл идёт до длины массива

       if lys[i] == element: #Нахождение элемента, равного введёному параметру element

           return i #Возвращаем значение данного индекса

   return -1

print(LinearSearch([1,2,3,4,5,2,1], 2)) #Вызов функции, и обьявление значений параметров

Answer 2

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

Вот пример реализации алгоритма линейного поиска с барьером на C++:

cppCopy code
#include <iostream>
#include <vector>

int linearSearchWithSentinel(const std::vector<int>& arr, int target) {
    int n = arr.size();
    
    // Добавляем барьер в конец массива
    arr.push_back(target);
    
    int i = 0;
    while (arr[i] != target) {
        i++;
    }
    
    // Возвращаем индекс найденного элемента или -1, если не найден
    if (i < n) {
        return i;
    } else {
        return -1;
    }
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7};
    int target = 5;
    
    int result = linearSearchWithSentinel(arr, target);
    
    if (result != -1) {
        std::cout << "Элемент " << target << " найден по индексу " << result << std::endl;
    } else {
        std::cout << "Элемент " << target << " не найден" << std::endl;
    }
    
    return 0;
}

Этот код добавляет элемент-барьер в конец массива и затем выполняет линейный поиск. Если элемент найден, он возвращает его индекс. Если элемент не найден, возвращается -1.

На Python, реализация будет похожей:

pythonCopy code
def linear_search_with_sentinel(arr, target):
    n = len(arr)
    
    # Добавляем барьер в конец массива
    arr.append(target)
    
    i = 0
    while arr[i] != target:
        i += 1
    
    # Возвращаем индекс найденного элемента или -1, если не найден
    if i < n:
        return i
    else:
        return -1

arr = [1, 2, 3, 4, 5, 6, 7]
target = 5

result = linear_search_with_sentinel(arr, target)

if result != -1:
    print(f"Элемент {target} найден по индексу {result}")
else:
    print(f"Элемент {target} не найден")

Обе реализации выполняют поиск элемента в массиве с барьером и возвращают индекс найденного элемента или -1, если элемент не найден.