Что ж, если вам нужно лучше, чем Binary, вы можете использовать эвристику, такую как поиск Ньютона, которая является производной от двоичного поиска, с перемещением границы разделения - каждый раз, когда значение больше, увеличивайте шаг, если он меньше, уменьшить его.
split = 0.5;
while(1)
{
point = lower+split*(upper-lower);
if(x>a[point])
{
lower = point;
split*= 1.2
}
else if(x<a[point])
{
upper=point;
split /=1.2
} else break;
}
Это предположительно дает лучшие результаты с наборами, которые имеют полиномиальные разметки и несвязанные множества. Это дает худшие результаты со случайными или линейными раскладками. Это также может привести к сбою с ростом сплита выше 1 без надлежащих мер безопасности.