🎯 Kotlin

Algorithmes de recherche en Kotlin : guide détaillé

Leçon 30 / 35 • Lecture complète de la théorie

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сложность бинарного поиска — 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 с игнорированием регистра или приводите строки к одному регистру.

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

Всегда проверяйте, отсортированы ли данные. Если вы не уверены — используйте линейный поиск или отсортируйте данные заранее. Бинарный поиск на неотсортированных данных даёт мусорные результаты.
Используйте встроенные методы, когда это возможно. Kotlin предоставляет binarySearch(), indexOf(), contains() — они оптимизированы и протестированы тысячами разработчиков. Не изобретайте велосипед.
Для сложных объектов реализуйте интерфейс Comparable. Это позволит использовать встроенный бинарный поиск с вашими классами.

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")
}

Используйте extension функции для переиспользования. Это делает код чище и удобнее.

// Добавляем метод поиска к любому списку 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))  // Использует бинарный поиск
}

Тестируйте граничные случаи: пустой список, список из одного элемента, поиск первого и последнего элемента, поиск отсутствующего элемента.
Для больших данных используйте бинарный поиск. Разница между O(n) и O(log n) становится огромной при n > 10 000.

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

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

Ответ: Данные должны быть отсортированы (по возрастанию или убыванию). Если массив не отсортирован, бинарный поиск может не найти элемент или вернуть неверный индекс.
Вопрос: Какова временная сложность линейного поиска в худшем случае?

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

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

Ответ: find возвращает первый элемент, удовлетворяющий условию (или null), а filter возвращает список всех подходящих элементов.
Вопрос: Почему в бинарном поиске используют left + (right - left) / 2 вместо (left + right) / 2?

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

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

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

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

Ответ: Нужно использовать indexOfFirst с условием: list.indexOfFirst { it.equals(target, ignoreCase = true) }.
Вопрос: Что такое «рекурсивный бинарный поиск» и в чём его недостаток?

Ответ:

← Précédent Algorithmes de tri en Kotlin : guide détaillé Suivant → Modèles de conception en Kotlin : guide détaillé