Задача с собеседования в Яндекс на бинарный поиск
#собеседование #interview #algo #алгоритмы #яндекс #binarysearch #бинарныйпоиск
Решил сделать отдельный пост, т.к. задача оказалась несколько сложнее, чем я изначально думал.
Задача: Какое число итераций (чтений из массива) потребуется, чтобы при помощи бинарного поиска гарантированно найти индекс заданного числа или установить его отсутствие в отсортированном массиве из 1000 чисел в худшем случае?
Решение: Бинарный поиск работает за O(log(n)) т.к. сокращает область поиска в два раза на каждой итерации. Я описывал бинарный поиск тут: Бинарный поиск. Худший случай это, например, поиск элемента на краях массива. Скажем у нас есть массив: [1, 2, 3, 4] и нам требуется найти 4. Нам потребуется 3 итерации.
Давайте попробует установить общую закономерность для любого размера массива.
Для размера 1: 1 итерация.
Для размера 2: 2 итерации.
Для размера 3: 2 итерации.
Для размера 4: 3 итерации.
Для размера 5, 6, 7: 3 итерации.
Для размера 8: 4 итерации.
Для размера 9, 10, 11, 12, 13, 14, 15: 4 итерации.
Для размера 16: 5 итераций.

Общая закономерность: Если размер массива это степень двойки (2, 4, 8, ...), То число итераций равно log2(n) + 1. Если размер не является степенью двойки, то нужно округлить log2(n) вверх до ближайшего целого: roundup(log2(n)).
Или За k-итераций бинарный поиск может обработать от 2^(k-1) до 2^k - 1 элементов массива: В виде отрезка это: [2^(k-1), 2^k) 2^k - не включительно

Теперь вернемся к задаче.
2^10 = 1024. Это больше, чем 1000. За 10 итераций бинарный поиск сможет обработать [2^(10-1), 2^10) = [512, 1024) элементов. Или от 512 до 1023 элементов. Т.е. ответ 10
Или 1000 не является степенью двойки, поэтому ответ: roundup(log2(n)) = 10
Давайте посмотрим как будет уменьшаться область поиска по итерациям для 1000:
1: 1000->500
2: 500->250
3: 250->125
4: 125->62
5: 62->31
6: 31->15
7: 15->7
8: 7->3
9: 3->1
10: Находим элемент или устанавливаем его отсутствие.
Ответ: 10

Спасибо всем, кто писал свои соображения в комментариях и чате.