питон либ луна питонлиб солнце progerlib цветок

Thema wechseln

Anmelden Registrierung
🎯 Kotlin

Suchalgorithmen in Kotlin: Eine ausführliche Anleitung

Lektion 30 / 35 • Vollständige Lektüre-Theorie

Что это такое и зачем? (аналогия из реальной жизни)

Представьте, что вы стоите перед огромным стеллажом в библиотеке, где на полках в хаотичном порядке разбросаны тысячи книг. Вам срочно нужна книга «Приключения Шерлока Холмса». Как вы будете её искать? Можно перебирать каждую книгу подряд — рано или поздно вы её найдёте, но это займёт целую вечность. А можно вспомнить, что библиотекарь расставил книги по алфавиту, открыть каталог, найти нужную букву «Х» и сразу пойти к нужному стеллажу.

В программировании происходит ровно то же самое. Алгоритм поиска — это чёткая инструкция, которая помогает компьютеру найти нужный элемент среди множества других. Компьютер, в отличие от человека, не может «пробежаться глазами» по списку — ему нужны точные команды: с чего начать, в каком порядке проверять, когда остановиться.

💡 Важно понимать: Алгоритмы поиска — это не просто «найти число в списке». Это основа работы поисковых систем (Google, Яндекс), баз данных, антивирусов, игр и даже вашего телефона, когда вы ищете контакт в записной книжке.

Представьте, что вы пришли в гости к другу, а он говорит: «Мой телефон где-то в этой комнате». Вы можете:

  • Линейный поиск: обшарить каждый угол, каждый ящик, каждую подушку — медленно, но гарантированно найдёте.
  • Бинарный поиск: спросить друга: «Телефон в левой половине комнаты или в правой?» — и так сужать круг поиска, пока не найдёте. Быстро, но комната должна быть «отсортирована» (например, все вещи разложены по полкам в алфавитном порядке).

В этой статье мы разберём оба этих подхода на языке Kotlin, научимся писать эффективный код и поймём, когда какой метод использовать.

Теория: как это работает изнутри

Чтобы понять алгоритмы поиска, нужно разобраться с двумя ключевыми понятиями: сложность алгоритма и структура данных.

Линейный поиск (Linear Search)

Это самый простой и интуитивно понятный алгоритм. Представьте, что у вас есть список чисел: [5, 3, 8, 1, 9, 2]. Вы хотите найти число 8. Алгоритм работает так:

  1. Берём первый элемент (5). Сравниваем с искомым (8). Не совпало.
  2. Берём второй элемент (3). Сравниваем. Не совпало.
  3. Берём третий элемент (8). Сравниваем. Совпало! Возвращаем индекс (2).

Всё гениально просто. Но есть нюанс: если элемент находится в самом конце списка или его вообще нет, алгоритму придётся проверить все элементы. В худшем случае — O(n) операций, где n — количество элементов. Это значит, что если в списке 1 000 000 элементов, может потребоваться 1 000 000 проверок.

Бинарный поиск (Binary Search)

Этот алгоритм работает по принципу «разделяй и властвуй». Но есть обязательное условие: данные должны быть отсортированы (по возрастанию или убыванию).

Представьте, что вы ищете слово в бумажном словаре. Вы не читаете его от корки до корки — вы открываете словарь примерно посередине, смотрите, с какой буквы начинаются слова на этой странице, и понимаете: «Моё слово на букву „П“ — оно правее». Вы отбрасываете левую половину и повторяете процесс с правой половиной.

Алгоритм шаг за шагом:

  1. Находим середину массива.
  2. Сравниваем искомый элемент с элементом в середине.
  3. Если совпало — отлично, возвращаем индекс.
  4. Если искомый элемент меньше — ищем в левой половине.
  5. Если больше — ищем в правой половине.
  6. Повторяем, пока не найдём или пока не останется пустой диапазон.

Сложность бинарного поиска — O(log n). Это невероятно быстро: для списка из 1 000 000 элементов потребуется всего около 20 проверок (потому что 2^20 ≈ 1 000 000).

⚠️ Критическое замечание: Бинарный поиск работает только на отсортированных данных. Если массив не отсортирован, бинарный поиск даст неверный результат или вообще не найдёт элемент, который на самом деле есть в списке.

Сравнение в таблице

Характеристика Линейный поиск Бинарный поиск
Требования к данным Любые (не требуется сортировка) Только отсортированные
Сложность (лучший случай) O(1) — элемент первый O(1) — элемент в середине
Сложность (худший случай) O(n) O(log n)
Простота реализации Очень простая Средняя (нужно следить за границами)
Где применяется Малые списки, неотсортированные данные Большие отсортированные массивы, базы данных

Синтаксис в Kotlin: все формы и варианты

Kotlin — современный язык, который предлагает несколько способов реализовать поиск. Мы рассмотрим как классические алгоритмические реализации, так и встроенные функции.

Базовые функции для работы с массивами и списками

В Kotlin есть встроенные методы, которые уже реализуют поиск «под капотом». Но чтобы понимать, как они работают, мы сначала напишем свои версии.

Метод Описание Пример
indexOf(element) Возвращает индекс первого вхождения элемента или -1 list.indexOf(5)
contains(element) Проверяет, есть ли элемент в коллекции list.contains(5)
binarySearch(element) Бинарный поиск (только для отсортированных списков) list.binarySearch(5)
find { условие } Находит первый элемент, удовлетворяющий условию list.find { it > 10 }
filter { условие } Возвращает список всех элементов, подходящих под условие list.filter { it > 10 }

Особенности Kotlin

  • Null-безопасность: В Kotlin нельзя просто так вернуть null — нужно явно указывать тип Int? (с вопросительным знаком). Это защищает от ошибок.
  • Extension функции: Можно добавлять свои методы к стандартным классам. Например, написать List.mySearch().
  • Range (диапазоны): Удобно работать с отрезками: 0..10, 0 until 10.

Примеры кода — от простого к сложному

Пример 1: Линейный поиск — базовая версия

// Самая простая реализация линейного поиска
fun linearSearch(array: IntArray, target: Int): Int {
    // Проходим по всем элементам массива
    for (i in array.indices) {
        // Если текущий элемент равен искомому
        if (array[i] == target) {
            return i  // Возвращаем его индекс
        }
    }
    return -1  // Если ничего не нашли, возвращаем -1
}

fun main() {
    val numbers = intArrayOf(10, 23, 45, 70, 11, 15)
    val target = 70
    
    val result = linearSearch(numbers, target)
    
    if (result != -1) {
        println("Элемент $target найден на индексе $result")
    } else {
        println("Элемент $target не найден")
    }
    // Вывод: Элемент 70 найден на индексе 3
}

Пример 2: Линейный поиск с использованием while

// Альтернативная реализация с циклом while
fun linearSearchWhile(array: IntArray, target: Int): Int {
    var index = 0
    // Пока не дошли до конца массива
    while (index < array.size) {
        if (array[index] == target) {
            return index
        }
        index++  // Переходим к следующему элементу
    }
    return -1
}

fun main() {
    val data = intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    println(linearSearchWhile(data, 7))  // Вывод: 6
    println(linearSearchWhile(data, 100)) // Вывод: -1
}

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

// Поиск работает не только с числами, но и с любыми типами
fun linearSearchString(list: List<String>, target: String): Int {
    for ((index, value) in list.withIndex()) {
        // Используем withIndex() для получения пары (индекс, значение)
        if (value == target) {
            return index
        }
    }
    return -1
}

fun main() {
    val fruits = listOf("яблоко", "банан", "вишня", "дыня", "ежевика")
    val searchFor = "дыня"
    
    val position = linearSearchString(fruits, searchFor)
    if (position != -1) {
        println("'$searchFor' найдено на позиции $position")
    } else {
        println("'$searchFor' отсутствует в списке")
    }
    // Вывод: 'дыня' найдено на позиции 3
}

Пример 4: Бинарный поиск — итеративная версия

// Классический бинарный поиск с циклом
fun binarySearchIterative(array: IntArray, target: Int): Int {
    var left = 0  // Левая граница поиска
    var right = array.size - 1  // Правая граница поиска
    
    // Пока левая граница не пересеклась с правой
    while (left <= right) {
        // Находим середину (безопасно от переполнения)
        val mid = left + (right - left) / 2
        
        when {
            array[mid] == target -> return mid  // Нашли!
            array[mid] < target -> left = mid + 1  // Ищем в правой половине
            else -> right = mid - 1  // Ищем в левой половине
        }
    }
    return -1  // Элемент не найден
}

fun main() {
    // ВАЖНО: массив должен быть отсортирован!
    val sortedArray = intArrayOf(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
    
    println(binarySearchIterative(sortedArray, 23))  // Вывод: 5
    println(binarySearchIterative(sortedArray, 1))   // Вывод: -1
    println(binarySearchIterative(sortedArray, 91))  // Вывод: 9
}

Пример 5: Бинарный поиск — рекурсивная версия

// Рекурсивная реализация — функция вызывает саму себя
fun binarySearchRecursive(array: IntArray, target: Int, left: Int, right: Int): Int {
    // Базовый случай: если границы сошлись, элемента нет
    if (left > right) return -1
    
    val mid = left + (right - left) / 2
    
    return when {
        array[mid] == target -> mid  // Нашли
        array[mid] < target -> binarySearchRecursive(array, target, mid + 1, right)  // Правая половина
        else -> binarySearchRecursive(array, target, left, mid - 1)  // Левая половина
    }
}

fun main() {
    val data = intArrayOf(1, 3, 5, 7, 9, 11, 13, 15, 17, 19)
    val target = 13
    
    val result = binarySearchRecursive(data, target, 0, data.size - 1)
    
    if (result != -1) {
        println("Рекурсивный поиск: элемент $target на индексе $result")
    } else {
        println("Элемент не найден")
    }
    // Вывод: Рекурсивный поиск: элемент 13 на индексе 6
}
🧠 Совет: Рекурсивная версия красивее и короче, но может вызвать переполнение стека при очень больших массивах (более 10 000 элементов). Итеративная версия безопаснее для продакшена.

Пример 6: Использование встроенной функции binarySearch()

// Kotlin предоставляет готовый метод для бинарного поиска
fun main() {
    // Создаём отсортированный список
    val sortedList = listOf(10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
    
    // Используем встроенный метод binarySearch
    val index = sortedList.binarySearch(70)
    
    if (index >= 0) {
        println("Элемент 70 найден на индексе $index")
    } else {
        // Если элемент не найден, binarySearch возвращает отрицательное число
        // (-insertionPoint - 1), которое показывает, куда можно вставить элемент
        println("Элемент не найден. Позиция для вставки: ${-index - 1}")
    }
    // Вывод: Элемент 70 найден на индексе 6
    
    // Поиск с компаратором (для сложных объектов)
    data class Person(val name: String, val age: Int)
    val people = listOf(
        Person("Анна", 25),
        Person("Борис", 30),
        Person("Виктор", 35)
    ).sortedBy { it.name }  // Обязательно сортируем по имени!
    
    val personIndex = people.binarySearch { it.name.compareTo("Борис") }
    println("Борис найден на индексе $personIndex")  // Вывод: 1
}

Пример 7: Поиск с кастомным условием (find и filter)

// Современный Kotlin-стиль с лямбда-выражениями
fun main() {
    val numbers = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    
    // find — находит ПЕРВЫЙ элемент, удовлетворяющий условию
    val firstEven = numbers.find { it % 2 == 0 }
    println("Первое чётное число: $firstEven")  // Вывод: 2
    
    // filter — находит ВСЕ элементы, удовлетворяющие условию
    val allEven = numbers.filter { it % 2 == 0 }
    println("Все чётные числа: $allEven")  // Вывод: [2, 4, 6, 8, 10]
    
    // Поиск по сложному условию
    data class Product(val name: String, val price: Double)
    val products = listOf(
        Product("Ноутбук", 75000.0),
        Product("Мышь", 1500.0),
        Product("Клавиатура", 3500.0),
        Product("Монитор", 25000.0)
    )
    
    // Ищем товары дешевле 5000 рублей
    val cheapProducts = products.filter { it.price < 5000.0 }
    println("Дешёвые товары: ${cheapProducts.map { it.name }}")
    // Вывод: Дешёвые товары: [Мышь, Клавиатура]
    
    // Ищем первый товар дороже 20000
    val expensiveProduct = products.find { it.price > 20000.0 }
    println("Первый дорогой товар: ${expensiveProduct?.name}")
    // Вывод: Первый дорогой товар: Ноутбук
}

Пример 8: Поиск в двумерном массиве

// Поиск элемента в матрице (двумерный массив)
fun searchInMatrix(matrix: Array<IntArray>, target: Int): Pair<Int, Int>? {
    // Проходим по строкам
    for (row in matrix.indices) {
        // Проходим по столбцам в текущей строке
        for (col in matrix[row].indices) {
            if (matrix[row][col] == target) {
                // Возвращаем пару (строка, столбец)
                return Pair(row, col)
            }
        }
    }
    return null  // Элемент не найден
}

fun main() {
    val grid = arrayOf(
        intArrayOf(1, 2, 3),
        intArrayOf(4, 5, 6),
        intArrayOf(7, 8, 9)
    )
    
    val result = searchInMatrix(grid, 5)
    if (result != null) {
        println("Элемент 5 найден на позиции (${result.first}, ${result.second})")
        // Вывод: Элемент 5 найден на позиции (1, 1)
    } else {
        println("Элемент не найден")
    }
}

Сравнение с Python: чем похоже и чем отличается

Если вы уже знакомы с Python, то заметите много общего, но есть и важные различия, которые нужно учитывать.

Аспект Kotlin Python
Объявление массива intArrayOf(1, 2, 3) или arrayOf(1, 2, 3) [1, 2, 3] или list((1, 2, 3))
Типизация Строгая статическая (тип указывается явно) Динамическая (тип определяется автоматически)
Индексация Только array[index] list[index] и срезы list[1:3]
Встроенный бинарный поиск list.binarySearch() — метод списка bisect.bisect_left() — модуль bisect
Возврат при отсутствии -1 или null -1 или исключение ValueError
Производительность Выше (компилируемый язык, JVM) Ниже (интерпретируемый язык)
Лямбда-выражения { it > 5 } lambda x: x > 5

Пример сравнения: линейный поиск на двух языках

// Kotlin
fun linearSearch(arr: IntArray, target: Int): Int {
    for (i in arr.indices) {
        if (arr[i] == target) return i
    }
    return -1
}
# Python
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
🔑 Ключевое отличие: В Kotlin нужно явно указывать тип возвращаемого значения (: Int), а в Python — нет. Kotlin проверяет типы на этапе компиляции, что предотвращает многие ошибки, но требует больше кода при объявлении.

Типичные ошибки и подводные камни

Ошибка 1: Забыли отсортировать массив для бинарного поиска

fun main() {
    val unsorted = intArrayOf(5, 2, 8, 1, 9, 3)
    // Забыли отсортировать!
    val result = unsorted.binarySearch(8)  // Может вернуть -1, хотя 8 есть в массиве!
    println(result)  // Непредсказуемый результат
}

Решение: Всегда сортируйте массив перед бинарным поиском: unsorted.sort().

Ошибка 2: Бесконечный цикл в бинарном поиске

fun badBinarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1
    while (left < right) {  // Ошибка: нужно <=, иначе пропустим последний элемент
        val mid = (left + right) / 2
        if (arr[mid] == target) return mid
        if (arr[mid] < target) left = mid  // Ошибка: нужно mid + 1
        else right = mid  // Ошибка: нужно mid - 1
    }
    return -1
}

Решение: Используйте while (left <= right) и корректно обновляйте границы: left = mid + 1, right = mid - 1.

Ошибка 3: Переполнение при вычислении середины

// Потенциально опасный способ
val mid = (left + right) / 2  // Если left и right большие, сумма может переполнить Int

// Безопасный способ
val mid = left + (right - left) / 2  // Никогда не переполнится

Ошибка 4: Путаница с индексацией

В Kotlin, как и в большинстве языков, индексация начинается с 0. Но новички часто думают, что первый элемент имеет индекс 1. Это приводит к ошибкам «off-by-one».

Ошибка 5: Использование == для сравнения строк без учёта регистра

fun main() {
    val names = listOf("Анна", "Борис", "Виктор")
    // Поиск чувствителен к регистру!
    println(names.indexOf("анна"))  // Вывод: -1 (не найдено)
    println(names.indexOf("Анна"))  // Вывод: 0 (найдено)
}

Решение: Используйте equals с игнорированием регистра или приводите строки к одному регистру.

Лучшие практики и советы профессионалов

  1. Всегда проверяйте, отсортированы ли данные. Если вы не уверены — используйте линейный поиск или отсортируйте данные заранее. Бинарный поиск на неотсортированных данных даёт мусорные результаты.
  2. Используйте встроенные методы, когда это возможно. Kotlin предоставляет binarySearch(), indexOf(), contains() — они оптимизированы и протестированы тысячами разработчиков. Не изобретайте велосипед.
  3. Для сложных объектов реализуйте интерфейс Comparable. Это позволит использовать встроенный бинарный поиск с вашими классами.
    4. data class Student(val name: String, val grade: Int) : Comparable<Student> {
    override fun compareTo(other: Student): Int {
        return this.grade.compareTo(other.grade)  // Сортировка по оценкам
    }
}

fun main() {
    val students = listOf(
        Student("Анна", 85),
        Student("Борис", 92),
        Student("Виктор", 78)
    ).sorted()  // Сортируем с использованием compareTo
    
    val index = students.binarySearch(Student("", 92))  // Ищем по оценке
    println("Студент с оценкой 92 на индексе $index")
}
  4. Используйте extension функции для переиспользования. Это делает код чище и удобнее.
    5. // Добавляем метод поиска к любому списку Int
fun List<Int>.smartSearch(target: Int): Int {
    return if (this == this.sorted()) {
        this.binarySearch(target)  // Если отсортировано — бинарный поиск
    } else {
        this.indexOf(target)  // Если нет — линейный
    }
}

fun main() {
    val list = listOf(1, 3, 5, 7, 9)
    println(list.smartSearch(5))  // Использует бинарный поиск
}
  5. Тестируйте граничные случаи: пустой список, список из одного элемента, поиск первого и последнего элемента, поиск отсутствующего элемента.
  6. Для больших данных используйте бинарный поиск. Разница между O(n) и O(log n) становится огромной при n > 10 000.

Вопросы для самопроверки

  1. Вопрос: Какое главное условие для применения бинарного поиска?

    Ответ: Данные должны быть отсортированы (по возрастанию или убыванию). Если массив не отсортирован, бинарный поиск может не найти элемент или вернуть неверный индекс.

  2. Вопрос: Какова временная сложность линейного поиска в худшем случае?

    Ответ: O(n), где n — количество элементов. В худшем случае (элемент в конце списка или отсутствует) придётся проверить все элементы.

  3. Вопрос: Что вернёт метод binarySearch(), если элемент не найден?

    Ответ: Отрицательное число, равное -(insertionPoint) - 1, где insertionPoint — индекс, на который можно вставить элемент, чтобы сохранить сортировку.

  4. Вопрос: В чём разница между методами find и filter в Kotlin?

    Ответ: find возвращает первый элемент, удовлетворяющий условию (или null), а filter возвращает список всех подходящих элементов.

  5. Вопрос: Почему в бинарном поиске используют left + (right - left) / 2 вместо (left + right) / 2?

    Ответ: Чтобы избежать переполнения целочисленного типа. Если left и right — большие числа (например, близкие к Int.MAX_VALUE), их сумма может выйти за пределы допустимого диапазона.

  6. Вопрос: Можно ли использовать бинарный поиск для списка строк?

    Ответ: Да, можно. Строки сравниваются лексикографически (по алфавиту). Главное — список должен быть отсортирован.

  7. Вопрос: Что произойдёт, если вызвать binarySearch() на неотсортированном списке?

    Ответ: Результат будет непредсказуемым. Метод может вернуть -1 (не найдено), хотя элемент есть, или вернуть неверный индекс. Ошибки компиляции не будет, но логика программы нарушится.

  8. Вопрос: Какой алгоритм поиска выбрать для списка из 5 элементов?

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

  9. Вопрос: Как в Kotlin найти индекс элемента в списке, игнорируя регистр символов?

    Ответ: Нужно использовать indexOfFirst с условием: list.indexOfFirst { it.equals(target, ignoreCase = true) }.

  10. Вопрос: Что такое «рекурсивный бинарный поиск» и в чём его недостаток?

    Ответ:

← Vorherige Sortieralgorithmen in Kotlin: Eine ausführliche An Weiter → Entwurfsmuster in Kotlin: Eine ausführliche Anleit