Comodo ordinamento e (binario?) alla ricerca di un array di coppie di numeri?

Question

Comodo ordinamento e (binario?) alla ricerca di un array di coppie di numeri?

#1 da (1 voti)

3

Quindi ho una matrice di coppie distinte di numeri interi positivi. Cioè, il mio array ha qualcosa del genere (per esempio):

{ (1,5) , (6,4), (5,3), (2,3), (2,4) }

E il mio compito è, per una data coppia (a,b) trovare (se esiste) la coppia (c,d) che ha c > a e d > b e, inoltre, è la coppia "minima" tale (cioè , c è minimo e, se ci sono più coppie che soddisfano questo con lo stesso c, allora d è minimo).

Quindi, ad esempio, se eseguo la query per l'array sopra per la coppia (1,1) , dovrebbe restituire (2,3) e se lo nutro (5,2) dovrebbe restituire (6,4) .

Ora il problema è che devo eseguire più query in modo che il tempo lineare non sia abbastanza buono. E la mia domanda è: c'è qualche modo in / qualsiasi legge con la quale posso "ordinare" un tale array in modo che possa poi eseguire ricerche binarie su di esso per trovare la mia risposta?

Stavo pensando che potrei semplicemente andare così: lascia che (x1,y1) e (x2,y2) siano due coppie da confrontare. Poi:

if(x1<x2)
    //pair 1 is smaller
else if(x1==x2 && y1<y2)
    //pair 1 is smaller
else
    //pair 2 is smaller

Questo sembrava risolvere la maggior parte dei casi, tuttavia .. se ho un array che assomiglia a questo:

{ .... (50,60) ..... }

dove (50, 60) è al centro dell'array. Ed eseguo una query per (40,70) per esempio. Il problema è che la coppia che voglio trovare potrebbe trovarsi sia a sinistra sia a destra di (50,60) (potremmo avere qualcosa come (45,90) a destra di (50, 60) , ma poi potremmo avere solo (x,10) a sinistra di (50,60) dove x<50 in modo che nessuna coppia a sinistra soddisfi la nostra condizione e dovrei guardare a destra).

Quindi per riassumerlo , se sto eseguendo una query per la coppia (x1,y1) e attraverso la mia ricerca binaria mi imbatto e l'elemento (x2,y2) che ha x1<x2 e y1>=y2 , quindi il mio algoritmo non può decidere se continuare a cercare a destra oa sinistra. Quindi devo cercare entrambi i lati e nel peggiore dei casi questo risulta essere O(n) .

Quindi c'è un modo più intelligente in cui puoi farlo? Qualsiasi aiuto sarebbe apprezzato. Grazie in anticipo:)

array binary search

posta Nu Nunu 24.11.2014 - 19:39

fonte

1 risposta

Leggi altre domande sui tag array binary search

Tabelle di ricerca di Entity Framework Qual è il modo corretto di pubblicare un runtime? Dovrebbe essere un singleton?

score 1 · Answer 1

Senza utilizzare alcuna memoria aggiuntiva, penso che il meglio che puoi fare sia una ricerca binaria sul primo elemento, quindi la ricerca lineare in avanti da lì per abbinare il secondo elemento. Questo ha prestazioni O (n) nel peggiore dei casi, ma dovrebbe essere vicino a O (log n) nel caso medio, specialmente dal momento che devi solo cercare in questo modo dopo aver colpito una direzione ambigua.

Se disponi di spazio di archiviazione sufficiente e di tempo per eseguire il calcolo preliminare, puoi creare una struttura di dati pre-ordinati bidimensionali, come nell'esempio seguente { (1,5) , (6,4), (5,3), (2,3), (2,4) } :

[(1, [(2,3), (5,3), (2,4), (6,4), (1,5)]),
 (2, [(2,3), (5,3), (2,4), (6,4)]),
 (5, [(5,3), (6,4)]),
 (6, [(6,4)])]

Quindi fai una ricerca binaria per 1, 2, 5 o 6 come primo elemento, che ti dà una lista ordinata dal secondo elemento, dove puoi fare un'altra ricerca binaria. Questo è O (n ²) per lo spazio, ma ti dà O (log n) in runtime.