Лінійний пошук

Лінійний або послідовний пошук – один з найпростіших алгоритмів пошуку елементів в масиві.

Алгоритм полягає у послідовному обході всіх елементів не впорядкованого масиву, як правило, зліва на право, та порівняння їх з ключовим значенням. Якщо значення елементу та ключа однакові, то пошук, в залежності від призначення, повертає значення чи індекс елементу.

Лінійний пошук використовується для знаходження:

• індексу заданого елементу масиву;
• індексів мінімального або максимального елементу;
• мінімального чи максимального значення в масиві.

Розглянемо методи розширення, які реалізують вище перераховані варіанти. Для того, щоб методи можна було застосовувати до різних типів даних, будемо використовувати універсальні шаблони(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();
    }
}