График Гигантские подсоединенного компонента

Question

я есть матрица вида

a b 8.0 
a d 0.1 
...... 

, где 1-й столбец является узел А, 2-й узел В и 3-й коэффициент корреляции я должен сделать программу, которая находит пороговое значение, таким образом, подключенную сеть имеет компонент Giant Connected, состоящий из 50-60% всех сетевых узлов. Я написал программу, которая с помощью двоичного поиска для порогового значения, как

if Giant Connected Component > 60% new threshold=oldthreshold + oldthreshold/2 
if Giant Connected Component < 50% new threshold=oldthreshold - oldthreshold/2 

Проблема заключается в том, что алгоритм также ищет порогов> 1 и/или < 0 .Как я могу справиться this.Or там лучше идея, как вычислить его?

Answer 1

Алгоритм, который вы описываете, не является бинарным поиском.

Чтобы правильно реализовать бинарный поиск, отследите два значения, min_threshold и max_threshold. Первоначально установите их на минимальные и максимально возможные пороговые значения. Затем на каждом шаге:

threshold = (min_threshold + max_threshold)/2 
if GCC(threshold) > 60%: # threshold is too low, update minimum 
    min_threshold = threshold 
else if GCC(threshold) < 50%: # threshold is too high, update maximum 
    max_threshold = threshold