Questo link ha fornito davvero alcuni spunti sull'idea che le implicazioni della ricerca binaria nei problemi di ottimizzazione dando il teorema principale. Non sono molto fiducioso di avere l'idea del teorema principale suggerito lì. Ci sono delle spiegazioni semplici, per le idee, espresse in quel tutorial?
Il requisito principale per la ricerca binaria di funzionare è che l'array deve essere ordinato. Fondamentalmente, il "teorema principale" generalizza quel requisito come necessario per la ricerca binaria generalizzata su funzioni invece di matrici. Dall'articolo:
Behind the cryptic mathematics I am really stating that if you had a yes or no question (the predicate), getting a yes answer for some potential solution x means that you'd also get a yes answer for any element after x. Similarly, if you got a no answer, you'd get a no answer for any element before x. As a consequence, if you were to ask the question for each element in the search space (in order), you would get a series of no answers followed by a series of yes answers.
Leggi altre domande sui tag problem-solving