Ответ
Алгоритм: Бинарный поиск в отсортированном списке.
Сложность: O(log n) по времени в худшем и среднем случае. O(1) по памяти (итеративная реализация).
Реализация на Dart:
/// Возвращает индекс [target] в отсортированном списке [sortedList].
/// Возвращает -1, если элемент не найден.
int binarySearch(List<int> sortedList, int target) {
int low = 0;
int high = sortedList.length - 1;
while (low <= high) {
// Избегаем переполнения для больших списков.
int mid = low + ((high - low) ~/ 2);
int midValue = sortedList[mid];
if (midValue == target) {
return mid; // Элемент найден.
} else if (midValue < target) {
low = mid + 1; // Ищем в правой половине.
} else {
high = mid - 1; // Ищем в левой половине.
}
}
return -1; // Элемент отсутствует.
}
void main() {
final list = [1, 3, 5, 7, 9, 11, 13];
print(binarySearch(list, 7)); // 3
print(binarySearch(list, 10)); // -1
}Почему O(log n)?
Алгоритм на каждом шаге делит область поиска пополам. В худшем случае он сделает столько делений, сколько раз n можно разделить на 2, пока не останется 1 элемент. Это и есть логарифм по основанию 2: log₂(n). Например, для списка из 1024 элементов потребуется не более 10 проверок (т.к. 2¹⁰ = 1024).
Ключевое условие: Список должен быть отсортирован. Для несортированного списка бинарный поиск неприменим, и потребуется линейный поиск со сложностью O(n).
Ответ 18+ 🔞
Давай разберём эту штуку, а то смотришь на код и думаешь — ёпта, что за манда с ушами? Но на самом деле всё гениально просто, если не тупить.
Представь, что у тебя есть телефонная книга. Ты же не будешь её листать с первой страницы, когда ищешь «Яковлев»? Нет, ты раскрываешь где-то посередине, смотришь — о, «Петров». Значит, нужно правее. Снова открываешь середину оставшейся части — бац, «Сидоров». Опять маловато. И так, пока не найдёшь. Вот это и есть бинарный поиск, только для чисел в списке.
В чём прикол? Скорость, блядь! Это не линейный поиск, где ты можешь в худшем случае перебрать овердохуища элементов. Здесь на каждом шаге ты отбрасываешь половину оставшегося списка. Получается, даже для списка в миллион элементов тебе хватит максимум 20 проверок. Ни хуя себе, да? Это потому что сложность O(log n). Логарифм — это просто ответ на вопрос: «Сколько раз нужно разделить число n пополам, чтобы получить 1?». Для 1 000 000 это всего около 20 раз. Волнение ебать!
Но есть важнейшее условие, чувак: список должен быть отсортирован. Иначе этот фокус не сработает. Если ты сунешь в него рандомный набор цифр, алгоритм просто накроется медным тазом и выдаёт хуйню. Придётся использовать линейный поиск и смириться с O(n).
Смотри на код:
int binarySearch(List<int> sortedList, int target) {
int low = 0;
int high = sortedList.length - 1;
while (low <= high) {
// Вот эта хитрая формула — чтобы не было переполнения, если low и high овердохуищные.
int mid = low + ((high - low) ~/ 2);
int midValue = sortedList[mid];
if (midValue == target) {
return mid; // Ура, нашли! Возвращаем индекс.
} else if (midValue < target) {
low = mid + 1; // Наш target правее, отрезаем левую половину.
} else {
high = mid - 1; // Наш target левее, отрезаем правую половину.
}
}
return -1; // Проехали. Элемента нет.
}Как это работает на примере? Берём [1, 3, 5, 7, 9, 11, 13], ищем 7.
- low=0, high=6. mid = 0 + (6-0)/2 = 3. sortedList[3] = 7. Ёбать-копать! Уже нашли! Возвращаем 3.
Ищем 10:
- low=0, high=6. mid=3. Число 7 < 10? Да. Значит, low = mid + 1 = 4. Теперь ищем в
[9, 11, 13]. - low=4, high=6. mid = 4 + (6-4)/2 = 5. sortedList[5] = 11. 11 > 10. Значит, high = mid - 1 = 4.
- low=4, high=4. mid = 4. sortedList[4] = 9. 9 < 10. low = mid + 1 = 5.
- Теперь low=5, high=4. Условие
low <= highложно. Выходим из цикла. Возвращаем -1. Да похуй, не повезло.
Итог: Алгоритм — пизда рулю. Быстрый, элегантный, но требует порядка в данных. Если список отсортирован — это твой лучший друг. Если нет — хуй с горы, ищи по-старинке.