Почему ленивый бинарный поиск?

Question

Сегодня кто-то спросил о Ленивых Бинарных Поисках. Не зная, что это было, я искал и нашел этот пост: Что такое Ленивый Бинарный Поиск? По сути, Ленивый Бинарный Поиск - это Бинарный Поиск, где вы сначала сравниваете неравенства, а сравниваете только на равенство один раз - в конце.

Какой смысл? При каких обстоятельствах проверяется, легко ли сделать A<B, но проверять, настолько ли сложен A=B, хотите ли вы избежать этого, если это возможно?

Answer 1

Это на единицу меньше сравнения за итерацию.

Конечно, это за счет худшего среднего времени выполнения (у вас нет возможности вернуться рано). ¹ Но иногдавсе, что вас волнует, - это время выполнения в наихудшем случае (например, жесткие приложения реального времени или конвейерная аппаратная реализация).

---

_{1.Хотя асимптотическая сложность не меняется.}

Answer 2

Одна из задач ленивого поиска - найти первый элемент в последовательности, равный цели (при условии, что цель находится в последовательности).

Если у вас есть несколько элементов, которые соответствуют цели, ленивый поиск даст вам любой из них.

Таким образом, binary_search библиотеки C ++ может быть реализован как не ленивый (и я думаю, что это обычно так), в то время как lower_bound не может.

Answer 3

Ну, просто в поиске "LAZY" вы пропускаете проверку на равенство каждый раз, когда сравниваете элемент X с центральным элементом. Только в самом конце вы проверяете равенство. Я полагаю, все, что вы делаете, - это сокращаете поиск на одно == условие.