Число поисковых запросов

Question

Как вы рассчитываете количество обращений для последовательного поиска, если запись присутствует, отсутствует или иногда присутствует?

А как насчет бинарного поиска?

Answer 1

Ну, во-первых, вы представляете (или рисуете на бумаге, если, как и я, вас бросает вызов воображению) список вещей для поиска - держите его простым, сделайте его упорядоченным списком целых чисел. Затем подумайте о целочисленном. Поместите свой карандаш (или мысль) на первый элемент в списке, согните большой палец с одной стороны и посчитайте 1 для себя. Если первый элемент - тот, который вам нужен, напишите 1 на другой лист бумаги, выберите другой номер и начните снова. Если первый номер не тот, который вы ищете, переместите свой карандаш по одному номеру, счет 2 и согните указательный палец на руке. Продолжайте, пока не найдете номер, который вы ищете, или нет.

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

Что касается бинарного поиска, посмотрите на элемент в середине списка. Count 1. Это элемент, который вы ищете? Если нет, это больше, чем тот элемент, который вы ищете? Если это так, то посмотрите на середину слева от списка, иначе посмотрите на средний элемент справа от списка. Повторите и подсчитайте, пока не найдете элемент, который вы ищете.

Работа с несколькими примерами с помощью карандаша и бумаги - отличный способ понять, что делает компьютер. И, по опыту, наступит день, когда вы обнаружите, что отлаживаете очень сложную часть кода таким образом, поэтому он будет стоять на вас хорошо, если вы когда-нибудь закончите профессиональное программирование.