Почему в бинарном поиске обратный возврат стоит больше, чем обратный?
Это не общая истина, и это не то, что хочет выразить цитата из GeeksforGeeks. Они хотят сказать, что , если известно, что (!) Обход назад по какой-то причине дороже, чем переход вперед (независимо от того, какой метод поиска вы используете), затем Jump Search может стать интересным выбором. Если нет, то вряд ли есть причина рассматривать эту альтернативу.
Приведенное ниже объяснение может быть улучшено следующим образом:
Двоичный поиск лучше имеет более сложную временную сложность , чем поиск по прыжкам, но преимущество по поиску прыжков заключается в том, что мы переходим обратно только один раз (для бинарного поиска может потребоваться до O (Log n) прыжков назад ; рассмотрим ситуацию, когдаэлемент для поиска является наименьшим элементом или меньше, чем наименьший). Таким образом, в системе, где бинарный поиск обходится дорого обратный обход обходится дороже, чем прямой обход , нам может потребоваться использование поиска перехода.
В примерах, когда перемещение в обратном направлении может стоить дороже, представьте данные, которые хранятся на лентах: при перемещении в прямом направлении лента может просто включаться и включаться при предоставлении данных, но с обратным перемещениемлента должна прекратить перемотку вперед (это стоит времени), выполнить перемотку и затем снова изменить направление (опять же, это требует дополнительного времени). Или возьмите дисководы, где диск должен пройти один полный оборот, чтобы добраться до места для чтения предыдущего блока.