Finden Sie den Index der ersten größer als oder gleiche Werte eines Vektors in einem anderen

Question

Ich habe zwei sortierte Vektoren x und y. Für jede y(i) möchte ich den ersten Index j so finden, dass y(i) >= x(j).

Beispiel:

x = [1 3 5 7 9 11 13 15] 
y = [3 4 5 9 10 11] 
result = [2 2 3 5 5 6] 

Was ist der effizienteste Weg, das zu tun?

Answer 1

Mit bsxfun und min in den Sinn kommt:

[~,result] = min(bsxfun(@gt, y(:), x(:).'), [], 2) 

Sie Vorteil der Rundfunk nehmen können, wo Sie zwei 2D-Matrizen mit y dupliziert werden über die Spalten erstellen und x über die Zeilen dupliziert werden. Ich nehme die gegenüber Problem, wo für jeden Wert von y, finden wir die erste Stelle, die kleinste ist. Das Ergebnis würde Ihnen somit die Lösung für jeden Wert in y geben. Wohlgemerkt, ich hätte das unter Verwendung von max angegangen und die Vergleichsoperation umgekehrt, aber ich mag diese Art besser.

Beispiel Run

>> x = [1 3 5 7 9 11 13 15] 

x = 

    1  3  5  7  9 11 13 15 

>> y = [3 4 5 9 10 11] 

y = 

    3  4  5  9 10 11 

>> [~,result] = min(bsxfun(@gt, y(:), x(:).'), [], 2) 

result = 

    2 
    3 
    3 
    5 
    6 
    6 

Minor Hinweis

Ich habe das Gefühl, Sie gehen diese für eine lineare Interpolation verwenden :)

Answer 2

Da der Vektor x teilweise bestellt wird (und daher monotonen), muss man das ganze x für jeden Eintrag in y transversieren. Der folgende Code sollte in MATLAB funktionieren:

lastOccurrence=1 
for i = 1:length(y) 
    for j = lastOccurrence:length(x) 
    if y(i)<x(j) 
     lastOccurence=j-1 
     result(i) = j-1 
     break 
    end 
    end 
end