Выполнение двоичного поиска

Question

Я выполняю двоичный поиск, скажем, мне нужно найти минимальное значение x, так что black_box(x) дает мне true результат.

Свойство black_box(x)

• Если black_box(x) дает мне так, то x+1,x+2,x+3,x+4....upto infinty все дает мне true

Для целочисленное значение это просто бинарный поиск

start=0; 
end = Max; 
ans=-1; 
while(start<=end){ 

    mid =(start+end)/2; 
    if(black_box(mid)): 
     end =mid-1 
     ans=mid; 
    else: start=mid+1; 
} 

Что делать, если я хочу floating point целое число до двух десятичных знаков, как я должен выполнять двоичный поиск?

Answer 1

Вы просто повторяете до start и end отличаются не более чем 0.01. Таким образом, условие остановки теперь:

while(end-start > 0.01){ 

Кроме того, как было указано в комментарии самостоятельно, вы не можете увеличения/уменьшения start и end в вашем алгоритме, так как индексы не являются дискретными. Полный алгоритм сейчас:

start=0; 
end = Max; 
ans=-1; 
while(end-start > 0.01){ 

    mid =(start+end)/2.0; 
    if(black_box(mid)): 
     end =mid 
     ans=mid; 
    else: start=mid; 
} 

Это работает, потому что на каждую итерацию start является нижней границей о точном значении и end является верхней границей от точного значения. Если оба значения не отличаются от 0.01, мы знаем, что он находится в диапазоне от start и end, а так как разница меньше 0,01, то это точный результат двумя десятичными знаками.

Тем не менее, ваш алгоритм неверен в том смысле, что, установив end = Inf, вы не можете работать с этим. Возможно, вы можете использовать максимальное представляемое значение или использовать экспоненциальный инкрементный поиск сначала как шаг предварительной обработки.