Последовательный поиск

Линейный или последовательный поиск – один из самых простых алгоритмов поиска элемента в массиве.

Алгоритм заключается в последовательном обходе всех элементов неупорядоченного массива, как правило, слева направо, и сравнения их с ключевым значением. Если значения элемента и ключа совпадают, то поиск, в зависимости от назначения, возвращает значение или индекс элемента.

Линейный поиск применяется для нахождения:

• индекса заданного элемента массива;
• индексов минимального или максимального элемента;
• минимального или максимального значения в массиве;

Рассмотрим методы расширения, которые реализуют выше перечисленные варианты. Для того, чтобы методы можно было применять к разным типам данных, будем использовать универсальные шаблоны(generics).

Для начала создадим статический класс, в который будем помещать все рассмотренные методы. По скольку не имеет смысла работать с пустым массивом, добавим в класс метод для проверки:

public static class ArrayExt
{    
    private static void CheckArray<T>(T[] a)
    {
        if (a == null)
        {
            throw new ArgumentNullException("Массив не может быть нулевым");
        }

        if (a.Length == 0)
        {
            throw new ArgumentException("Длина массива должна быть больше нуля");
        }
    }
}

Метод для линейного поиска по значению

Принимает в качестве аргументов массив и искомое значение, а возвращает индекс найденного элемента, или -1 в случае неудачи. Тип данных ограничен структурами для которых реализован интерфейс сравнения IEquatable.

public static int LinearSearch<T>(this T[] a, T key) where T : struct, IEquatable<T>
{
    CheckArray(a);

    for (int i = 0; i < a.Length; ++i)
    {
        // сравниваем текущее значение с искомым
        if (a[i].Equals(key))
        {
            return i;
        }
    }
    //если ничего не нашли
    return -1;
}

Поиск индекса минимального элемента

Позволяет найти индекс первого наименьшего значения в массиве. Тип входящих аргументов ограничен структурами с реализованным интерфейсом IComparable.

public static int IndexOfMin<T>(this T[] a) where T : struct, IComparable<T>
{
    CheckArray(a);

    int indexMin = 0;
    T min = a[0];
    for (int i = 1; i < a.Length; ++i)
    {
        if (a[i].CompareTo(min) < 0) //аналог записи a[i] < min, для обобщений
        {
            min = a[i];
            indexMin = i;
        }
    }

    return indexMin;
}

Поиск минимального значения массива

Позволяет найти наименьший элемент в массиве.

public static T MinValue<T>(this T[] a) where T : struct, IComparable<T>
{
    CheckArray(a);

    T min = a[0];
    for (int i = 1; i < a.Length; ++i)
    {
        if (a[i].CompareTo(min) < 0)
        {
            min = a[i];
        }
    }

    return min;
}

Поиск индекса максимального элемента

Позволяет найти позицию первого наибольшего значения.

public static int IndexOfMax<T>(this T[] a) where T : struct, IComparable<T>
{
    CheckArray(a);

    int indexMax = 0;
    T max = a[0];
    for (int i = 1; i < a.Length; ++i)
    {
        if (a[i].CompareTo(max) > 0) //аналог записи a[i] > max, для обобщений
        {
            max = a[i];
            indexMax = i;
        }
    }

    return indexMax;
}

Поиск максимального значения массива

Позволяет найти наибольший элемент в массиве.

public static T MaxValue<T>(this T[] a) where T : struct, IComparable<T>
{
    CheckArray(a);

    T max = a[0];
    for (int i = 1; i < a.Length; ++i)
    {
        if (a[i].CompareTo(max) > 0)
        {
            max = a[i];
        }
    }

    return max;
}

Использование методов для последовательного поиска

class Program
{
    static void Main(string[] args)
    {
        int[] arr = { 5, 6, 2, 4, 9, 0, 1, 3, 7, 8 };

        var index = arr.LinearSearch(22);
        if (index == -1)
        {
            Console.WriteLine("Элемент не найден");
        }

        Console.WriteLine($"Индекс элемента со значением 4 равен {arr.LinearSearch(4)}");
        Console.WriteLine($"Минимальный элемент массива: индекс {arr.IndexOfMin()}; значение {arr.MinValue()};");
        Console.WriteLine($"Максимальный элемент массива: индекс {arr.IndexOfMax()}; значение {arr.MaxValue()};");

        Console.ReadLine();
    }
}