Valore minimo nell'intervallo

Question

Vorrei trovare il valore più basso in un intervallo.
Devo ripetere iterate ogni volta o esiste un metodo dinamico?

Diciamo che ho array di input:

index: 0 1 2 3 4 5 6 7 
value: 1 4 6 1 6 7 2 3 

e poi ho dovuto scegliere più piccolo nella gamma < a, b> (compreso). Ad esempio:

min(0,7) = 1 
min(0,2) = 1 
min(4,6) = 2 
min(1,2) = 4 

Sono interessato alla soluzione più veloce, sarebbe il migliore per ottenere i risultati in tempo costante.

L'array non verrà modificato nel frattempo.

Answer 1

Se si desidera eseguire più query sullo stesso insieme di numeri, sarà necessario creare un Cartesian Tree.

alberi cartesiane possono essere utilizzati come parte di una struttura di dati efficiente per le query minimo raggio, un problema intervallo di ricerca che coinvolgono le query che richiedono il valore minimo in una sottosequenza contigua della sequenza originale.

Come dice l'articolo, le query possono essere eseguite in tempo costante.

Answer 2

Questa è un'attività standard. È possibile utilizzare la funzionalità della libreria std. Dovrebbe essere il più veloce possibile. L'esempio da here:

#include <iostream>  // std::cout 
#include <algorithm> // std::min_element, std::max_element 

int main() { 
    int myints[] = {3,7,2,5,6,4,9}; 

    std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n'; 

    return 0; 
} 

---

P.S. Non è possibile ottenere risultati in un tempo costante, poiché se è necessario un minimo tra N elementi è necessario controllare ciascun elemento. La complessità minima del task è O (N).

Answer 3

È possibile provare la (cosa non è sicuro se mi manca) a seguito

Se si è permesso qualche pre-elaborazione, allora si può avere una serie di minimi locali (valli).

Questo array deve essere ordinato secondo i rispettivi indici.

Una volta ottenuto un intervallo, eseguire una ricerca binaria dell'indice inferiore nell'array dei minimi. Scegli il più grande in quella matrice. say I1

Quindi eseguire una ricerca binaria dell'indice più alto nell'array dei minimi. Scegli il più piccolo in quella matrice. dire I2

Se I2> = I1, allora almeno un minimo locale esiste nell'intervallo. Basta confrontare i valori ai minimi in quell'intervallo e ai limiti per ottenere la risposta.

Altrimenti, non esiste un minimo locale nell'intervallo. In questo caso, il minimo deve essere al limite dell'intervallo. Basta confrontare i due valori e ottenere quello inferiore.

Answer 4

Per questa domanda è possibile utilizzare segment tree. This è uno dei migliori tutorial sull'intervallo di segmenti e nell'intervallo minimo di query.

Fornisco l'implementazione JAVA e il codice è autoesplicativo, per favore fatemi sapere se avete dei dubbi.

public class SegmentTree { 

    private int[] array; 
    private int length; 

    public static SegmentTree initialize(int[] a) { 
     return new SegmentTree(a); 
    } 

    private SegmentTree(int[] a) { 
     length = a.length - 1; 
     int l = (int) (Math.log(a.length)/Math.log(2)); 
     l = (int) (Math.pow(2, l + 1) * 2 - 1); 
     array = new int[l]; 
     initialize(a, 0, a.length - 1, 0); 
    } 

    private int initialize(int[] a, int p, int r, int index) { 
     if (p == r) { 
      array[index] = a[p]; 
      return a[p]; 
     } 
     int q = p + (r - p)/2; 
     array[index] = Math.min(initialize(a, p, q, 2 * index + 1), initialize(a, q + 1, r, 2 * index + 2)); 
     return array[index]; 
    } 

    public int findMin(int p, int r) { 
     return _findMin(p, r, 0, length, 0); 
    } 

    private int _findMin(int qs, int qe, int ss, int se, int i) { 
     if (qs <= ss && se <= qe) { 
      return array[i]; 
     } 
     if (qs > se || qe < ss) { 
      return Integer.MAX_VALUE; 
     } 
     int q = ss + (se - ss)/2; 
     return Math.min(_findMin(qs, qe, ss, q, 2 * i + 1), _findMin(qs, qe, q + 1, se, 2 * i + 2)); 
    } 

    private void print() { 
     int index = 0; 
     for (int k : array) { 
      System.out.println(index + ":" + k); 
      index++; 
     } 
    } 

    public static void main(String[] args) { 
     int[] a = {1, 34, 5, 6, 78, 5, 67, 89}; 
     SegmentTree s = initialize(a); 
     System.out.println(s.findMin(2, 4)); 
    } 
}