Ho una lista ordinata, diciamo 1, 6, 10, 15, 16, 18, 30, 50.
Come trovo i primi tre elementi che si trovano nell'intervallo inferiore a n, per esempio 3.
Ad esempio nell'elenco precedente, 15, 16 e 18 è la risposta. È possibile arrivare a questo in meglio di O (n)?
Non puoi semplicemente sottrarre un [2] -a [0] e vedere se meno di N. Se è così, c'è la tua risposta. In caso contrario, prova un [3] -a [1] e vedi se meno di N. Iterate fino a quando non lo trovi o finisci. Potenzialmente richiede confronti N-2.
Leggi altre domande sui tag algorithms