Приведи пример реализации алгоритма поиска элемента в отсортированном массиве

Реализация поиска в отсортированном массиве: бинарный поиск

Для отсортированного массива классическим и оптимальным алгоритмом поиска является бинарный поиск (Binary Search). Этот алгоритм основан на принципе «разделяй и властвуй» и имеет логарифмическую сложность O(log n), что делает его значительно эффективнее линейного поиска O(n) для больших массивов.

Основной принцип бинарного поиска

Алгоритм работает путем многократного деления отсортированного массива пополам:

1. Сравниваем искомый элемент с элементом в середине массива
2. Если значения равны - поиск завершен
3. Если искомый элемент меньше среднего - продолжаем поиск в левой половине
4. Если искомый элемент больше среднего - продолжаем поиск в правой половине
5. Процесс повторяется до нахождения элемента или исчерпания диапазона поиска

Классическая реализация на C#

public class BinarySearch
{
    // Итеративная реализация
    public static int SearchIterative(int[] sortedArray, int target)
    {
        if (sortedArray == null || sortedArray.Length == 0)
            return -1;
        
        int left = 0;
        int right = sortedArray.Length - 1;
        
        while (left <= right)
        {
            // Используем безопасное вычисление середины для избежания переполнения
            int middle = left + (right - left) / 2;
            
            if (sortedArray[middle] == target)
                return middle; // Элемент найден
            else if (sortedArray[middle] < target)
                left = middle + 1; // Ищем в правой половине
            else
                right = middle - 1; // Ищем в левой половине
        }
        
        return -1; // Элемент не найден
    }
    
    // Рекурсивная реализация
    public static int SearchRecursive(int[] sortedArray, int target, int left, int right)
    {
        if (left > right)
            return -1;
            
        int middle = left + (right - left) / 2;
        
        if (sortedArray[middle] == target)
            return middle;
        else if (sortedArray[middle] < target)
            return SearchRecursive(sortedArray, target, middle + 1, right);
        else
            return SearchRecursive(sortedArray, target, left, middle - 1);
    }
    
    // Обертка для рекурсивного метода
    public static int SearchRecursiveWrapper(int[] sortedArray, int target)
    {
        if (sortedArray == null)
            return -1;
            
        return SearchRecursive(sortedArray, target, 0, sortedArray.Length - 1);
    }
}

Пример использования

class Program
{
    static void Main(string[] args)
    {
        int[] sortedNumbers = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
        int target = 11;
        
        // Итеративный поиск
        int resultIterative = BinarySearch.SearchIterative(sortedNumbers, target);
        Console.WriteLine($"Итеративный поиск: элемент {target} найден по индексу {resultIterative}");
        
        // Рекурсивный поиск
        int resultRecursive = BinarySearch.SearchRecursiveWrapper(sortedNumbers, target);
        Console.WriteLine($"Рекурсивный поиск: элемент {target} найден по индексу {resultRecursive}");
        
        // Поиск отсутствующего элемента
        int missingResult = BinarySearch.SearchIterative(sortedNumbers, 8);
        Console.WriteLine($"Поиск отсутствующего элемента: результат {missingResult} (ожидаемо -1)");
    }
}

Варианты и оптимизации

На практике бинарный поиск имеет несколько важных модификаций:

1. Поиск первого вхождения (для массивов с дубликатами)

public static int FindFirstOccurrence(int[] sortedArray, int target)
{
    int left = 0;
    int right = sortedArray.Length - 1;
    int result = -1;
    
    while (left <= right)
    {
        int middle = left + (right - left) / 2;
        
        if (sortedArray[middle] == target)
        {
            result = middle;
            right = middle - 1; // Продолжаем искать в левой части
        }
        else if (sortedArray[middle] < target)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
    }
    
    return result;
}

2. Поиск ближайшего элемента (если точного совпадения нет)

public static int FindClosest(int[] sortedArray, int target)
{
    if (sortedArray == null || sortedArray.Length == 0)
        return -1;
        
    int left = 0;
    int right = sortedArray.Length - 1;
    
    while (left <= right)
    {
        int middle = left + (right - left) / 2;
        
        if (sortedArray[middle] == target)
            return middle;
            
        if (sortedArray[middle] < target)
            left = middle + 1;
        else
            right = middle - 1;
    }
    
    // После завершения цикла left указывает на позицию для вставки
    // Возвращаем ближайший элемент
    if (left == sortedArray.Length)
        return sortedArray.Length - 1;
    if (left == 0)
        return 0;
        
    // Выбираем ближайший из двух соседних элементов
    return Math.Abs(sortedArray[left] - target) < Math.Abs(sortedArray[left - 1] - target) 
        ? left : left - 1;
}

Ключевые особенности реализации

• Безопасное вычисление середины: использование left + (right - left) / 2 вместо (left + right) / 2 предотвращает возможное переполнение при работе с большими массивами
• Граничные условия: всегда проверяем входные параметры на null и пустоту
• Универсальность: алгоритм работает с любыми типами данных, поддерживающими сравнение
• Предусловие: массив должен быть отсортирован по возрастанию

Производительность

• Временная сложность: O(log n)
• Пространственная сложность:
  • Итеративная версия: O(1)
  • Рекурсивная версия: O(log n) из-за стека вызовов

Встроенные средства .NET

В реальных проектах часто используются встроенные методы:

// Использование Array.BinarySearch
int[] array = { 1, 3, 5, 7, 9 };
int index = Array.BinarySearch(array, 5);

// Использование List.BinarySearch
List<int> list = new List<int> { 1, 3, 5, 7, 9 };
int listIndex = list.BinarySearch(5);

Практические рекомендации

1. Выбор реализации: итеративная версия предпочтительнее из-за отсутствия накладных расходов на рекурсию
2. Проверка отсортированности: в production-коде стоит добавлять проверку отсортированности массива или документально указывать это требование
3. Работа с дубликатами: если в массиве могут быть дубликаты, используйте модифицированные версии поиска
4. Generic-версия: для большей гибкости можно создать generic-версию метода с ограничением where T : IComparable<T>