Ogni volta che eseguo la ricerca binaria in modo iterativo, sono sempre confuso se utilizzare while (low < high) o while(low <= high).Condizione di terminazione della ricerca binaria
Sebbene funzionino entrambi, ma qualcuno può dirmi quale potrebbe essere il vantaggio pratico di uno rispetto all'altro?
Le due condizioni di terminazione che si stanno elencando sono spesso utilizzate a seconda che il basso e l'alto siano inclusivi o esclusivi. Se i tuoi limiti sono inclusivi, quando bassa = alta c'è un elemento rimasto nella matrice da controllare e il ciclo interno dovrebbe essere eseguito un'altra volta. Pertanto, è necessario verificare se il livello basso è ≤ alto. D'altra parte, se bassa è inclusiva e alta è esclusiva, quando bassa = alta hai esaurito tutti gli elementi e hai finito, quindi un test del modulo basso < alto è più appropriato.
Grazie. Pensi che questo possa essere un buon esempio pratico? Supponendo che ogni volta che aggiorno 'high' come' mid-1' e 'low' come' mid + 1', quindi basso basso ed esclusivo supponiamo che l'elemento sia all'interno dell'array quindi è sicuro terminarlo senza controllando l'ultimo elemento. Tuttavia, i limiti inclusivi controllano in modo sicuro l'ultimo elemento e vengono utilizzati nel caso in cui non siamo sicuri se l'elemento esiste? – Zanko
Suppongo che sia valido, ma il caso più comune è solo nella convenzione di chiamata. Stai inizializzando in alto per essere l'indice dell'ultimo elemento dell'array (limiti inclusi), o la lunghezza dell'array (limiti esclusivi)? – templatetypedef
'lo = 0' e' hi = nums.length - 1' – Zanko
dipende dal modo in cui si aggiornano 'bassi' e' alti' – svs