Trova l'elemento intermedio negli array uniti in O (logn)

Question

Abbiamo due array ordinati della stessa dimensione n. Chiamiamo l'array a e b.

Come trovare l'elemento centrale in un array ordinato unito da aeb?

Example: 

n = 4 
a = [1, 2, 3, 4] 
b = [3, 4, 5, 6] 

merged = [1, 2, 3, 3, 4, 4, 5, 6] 
mid_element = merged[(0 + merged.length - 1)/2] = merged[3] = 3 

casi più complicati:

Caso 1:

a = [1, 2, 3, 4] 
b = [3, 4, 5, 6] 

Caso 2:

a = [1, 2, 3, 4, 8] 
b = [3, 4, 5, 6, 7] 

Caso 3:

a = [1, 2, 3, 4, 8] 
b = [0, 4, 5, 6, 7] 

Caso 4:

a = [1, 3, 5, 7] 
b = [2, 4, 6, 8] 

---

Tempo di percorrenza: O (log n). Qualche idea?

Answer 1

Guarda al centro di entrambi gli array. Diciamo che un valore è più piccolo e l'altro è più grande.

Scarta la metà inferiore dell'array con il valore inferiore. Scartare la metà superiore dell'array con il valore più alto. Ora siamo rimasti con metà di ciò che abbiamo iniziato.

Risciacquo e ripetizione fino a quando non viene lasciato un solo elemento in ogni matrice. Restituisce il più piccolo di quei due.

Se i due valori medi sono uguali, quindi selezionare arbitrariamente.

Crediti: Bill Li's blog

Answer 2

Compito piuttosto interessante. Non sono sicuro di O (logn), ma la soluzione O ((logn)^2) è ovvia per me. Se conosci la posizione di alcuni elementi nel primo array, puoi trovare quanti elementi sono più piccoli in entrambi gli array, quindi questo valore (sai già quanti elementi più piccoli sono nel primo array e puoi trovare il conteggio di elementi più piccoli nel secondo array usando ricerca binaria - quindi riassumi questi due numeri). Quindi, se sai che il numero di elementi più piccoli in entrambi gli array è inferiore a N, dovresti guardare nella metà superiore del primo array, altrimenti dovresti passare alla metà inferiore. Quindi otterrai una ricerca binaria generale con ricerca binaria interna. Complessità complessiva sarà O ((logn)^2)

Nota: se non si trova la mediana nella prima matrice, avviare la ricerca iniziale nella seconda matrice. Ciò non avrà un impatto sulla complessità

Answer 3

Quindi, avendo n = 4 e = [1, 2, 3, 4] e b = [3, 4, 5, 6]

È conoscere in anticipo la posizione k-es dell'array di risultati in base a n, che è uguale a n. L'elemento n-esimo risultante potrebbe essere nel primo array o secondo. Supponiamo innanzitutto che l'elemento sia nel primo array, quindi fare la ricerca binaria prendendo l'elemento centrale da [l, r], all'inizio l = 0, r = 3; Quindi, prendendo l'elemento intermedio, sai quanti più elementi dello stesso array sono più piccoli, che è il mezzo - 1. Sapendo che l'elemento middle-1 è inferiore e sapendo che hai bisogno dell'elemento n-esimo potresti avere [n - (middle-1)] elemento th dal secondo array per essere più piccolo, più grande. Se questo è maggiore e l'elemento precedente è più piccolo di quello che ti serve, se è maggiore e precedente è anche maggiore dobbiamo L = medio, se è più piccolo r = medio. Fare lo stesso per il secondo array nel caso in cui non si trovasse la soluzione per prima. Nel registro totale (n) + registro (n)