in ,

Я загадал число от 1 до 1000000. Как угадать за 20 попыток. Отвечает программист

Привет, друзья. Читатели моего канала знают, что я фрилансер и работаю удалённо. Так вот сегодня мы проводили собеседования с разными программистами. В компании появилась вакансия для удалённого разработчика и мы общались с кандидатами.

Я люблю задавать конкретные вопросы, связанные с разработкой и логикой. Но больше всего меня волнует, умеет ли кандидат работать с большими базами данных.

Представьте себе, что есть книга, в которой миллион страниц. А теперь представьте, что таких книг у вас миллиард. Вот про такое, можно сказать — большая база данных.

А теперь мой вопрос для кандидата. Простой вопрос, ставит многих в тупик. Я загадал число от 1 до 1 000 000. Как угадать за 20 попыток?

Здесь нет никакого подвоха, потому что программист, который действительно работал с большими базами данных, сразу поймёт о чём я спрашиваю.

Я вам хочу рассказать, как можно угадать число за 20 попыток. 20 это максимум. Иногда вы будете угадывать быстрее.

Давайте, чтобы не углубляться в термины программистов, возьмём пример с книгой, у которой есть 1 000 000 страниц. И вам нужно найти страницу, на которой написано слово «Вебзнайка». Вы точно знаете, что только на одной странице встречается это слово.

Как вы будете искать? Скорее всего, вы будете открывать страницы по очереди и читать. Согласитесь, это может занять много времени. По теории вероятности вам потребуется около 500 000 попыток, чтобы найти слово «Вебзнайка».

База данных, если программист понимает, что делает, может позвать помощника, которого зовут «Индекс». Он будет говорить сразу, есть ли на странице то, что вы ищете. Вам даже не потребуется читать. И ещё, как бонус будет указывать вам, где искать дальше.

Пример. Представим, что я — это «Индекс». И вы ищете слово «Вебзнайка», которое написано на странице 678 123.

Вы открываете страницу номер 500 000.

— На этой странице нет. Смотрите на следующих. — Отвечаю я.

Обратите внимание. Вам нужно искать в соответствии с простым алгоритмом. Любая попытка, это всегда середина. Теперь вы знаете, что слово написано на какой-то странице от 500 000 до 1 000 000. Вы снова должны открыть книгу на середине этого диапазона.

То есть, следующая ваша попытка — страница 750 000.

— Снова нет. Ищите на предыдущих страницах. — Отвечаю я.

Ага теперь вы знаете, что слово между 500 000 и 750 000 страницами. Теперь вам снова нужно отрыть книгу на середине.

Вы пробуете поискать на странице 625 000.

— Здесь нет. Но есть на одной из следующих. — Отвечаю я.

Теперь вы знаете, что слово написано где-то между 625 000 и 750 000 страницами. Как узнать следующую страницу, которую нужно открыть, чтобы была середина? Всё просто:

750 000 — 625 000 = 125 000.
125 000 / 2 = 62 500.
625 000 + 62 500 = 687 500.

Вот 687 500 это и будет середина. Дальше я снова отвечу больше или меньше.

В общем, при таком подходе вы всегда угадаете номер страницы максимум за 20 попыток.

Можете попробовать дома с кем-нибудь из близких. Только имейте под рукой листочек и калькулятор, чтобы точно вычислять середину диапазона. А человек, загадавший число, должен говорить вам, больше или меньше.

Как это работает? Тут снова всё просто. Сколько раз 1 000 000 нужно поделить на 2, чтобы получить 1? Правильно, всего 20 раз.

Вы можете найти онлайн-калькулятор логарифмов. Берите число миллион и основание 2. Получите результат 20.

Если вы заходите угадать число от одного до миллиарда — вам потребуется 30 попыток. Число больше, а попыток добавилось всего 10.

В программировании так происходит поиск по базе данных. Уважаемый «Индекс» всегда помогает находить всё быстро. К сожалению, не все программисты знают о его существовании.

Читать и комментировать в Яндекс Дзен.

Как мой смартфон стал веб-камерой в подъезде на одну ночь. Отвечает программист

Почему я не верю в успех операционной системы для смартфонов от «Huawei». Отвечает программист