Решила почитать что-то легкое и полезное. Тем более на эту книгу много хороших отзывов.
Кстати, буквально сегодня в тиктоке увидела девушку, которая учила алгоритмы по этой книге и в комментариях все писали, что книга плохая. А я вот пока что так не думаю. Читается легко и объясняется как для маленького тупенького ребёнка — выглядит как признак хорошей книги. :)
Заметки:
- Алгоритм — это набор инструкций для выполнения какой-либо задачи.
- Хорошая новость — скорее всего реализация каждого алгоритма доступна на любом языке.
- Плохая новость — надо понимать сильные и слабые стороны алгоритмов. Эх, не получится взять первый попавшийся.
- Простой (тупой) поиск — перебираем все элементы подряд. Если из 100 элементов нам нужен 99-й, то мы дойдем до него перебрав первые 98. Звучит не очень эффективно, правда? Особенно, если таких элементов миллион.
- Бинарный поиск — на входе нам дают отсортированный список. Если элемент найден, то возвращается позиция, если не найден, то null. Кстати, на одном из собеседований у меня спрашивали, а что такое бинарный поиск.
- Бинарный поиск начинает с середины. Например, есть список от 1 до 100 и мы хотим найти элемент 99. Раз начинаем с середины, то первое число, которое проверяем — 50. И мы знаем, что массив отсортирован и число 99 больше 50. Отсеяли сразу половину: которая перед 50. У нас остался список от 50 до 100. Теперь берем снова середину из оставшихся — 75. 99 все еще больше. Снова сокращаем список и теперь он у нас всего из 25 элементов от 75 до 100. Берем еще середину — 88. 99 все еще больше, так что повторяем алгоритм. Следующее — 93. Всё ещё не подходит. Дальше — 96 и снова не подходит. После сокращения листа берем из середины 98 — больше. И у нас остается список из двух чисел: 99 и 100. Берем середину и вуаля — 99. В тупом поиске мы бы перебрали 98 элементов, а тут всего 6.
- В бинарном поиске мы каждый раз загадываем число в середине и исключаем половину оставшихся. Все тут любят приводить в пример телефонную книгу: если мы хотим найти телефон Николая, то мы не будем листать с самого начала, где буква А.
- Чтобы узнать количество шагов в бинарном поиске мы пользуемся формулой log2 (количество элементов). Если не помните как считать логарифмы, то это просто степень числа, которое стоит, и основания. Т.е. в нашем случае это степень двойки. Например, для 100 элементов бинарный поиск в худшем случае log2 100. Если совсем проще: считаем, в какой степени двойка станет числом из нашего списка.
- Вернемся к списку с элементами от 1 до 100. Мы хотим посчитать количество шагов без реализации алгоритма, чтобы доказать миддлу, который нас проверяет, что это лучше перебора. Считаем степень: 2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32, 2^6 = 64, 2^7 = 128. Уже большее число. Значит в худшем случае поиск займет 7 шагов. Можете потренироваться и посчитать, сколько шагов займет поиск для числа 240_123 из 250 000 элементов.
- Бинарный поиск работает только если список отсортирован. Это важно!
- Как написать алгоритм для поиска: у нас будет метод, который на вход получает список элементов и элемент, который надо найти.
- Каждый раз проверяем значение посередине. Если список нечетный, то округляется в меньшую сторону.
Ответ на пункт 9: 18
Сам алгоритм. Можно просто скопировать и запустить. Он работает. Обратите внимание, что в ответе будет не 55, а 54. Это потому что в массиве нумерация с 0.
У вас могли возникнуть вопросы, почему середину считаем так middle = start + ((end - start) / 2), а не просто (end - start) / 2, ведь мы все со школы знаем, что для середины надо просто вычесть из конца начало и разделить на два. Посмотрим на примере.
Видно разницу? Если просто вычитать и делить, то мы находим середину. Для 100 будет 50 — и это выглядит правильно. Но если мы уже отбросили 10 чисел и хотим найти середину от 10 до 100, то вычитание и деление получит 45, потому что от 10 до 100 — это 90 и при делении на 2 получим 45. Поэтому мы и прибавляем start, чтобы получить середину с учетом сдвига.
