✔ Nähesten Wert finden

[Sovok]

Ich möchte den Wert finden der ab besten zu dem gesuchten Wert passt.
Und natürlich wenn möglich nicht mit einer naiven linearen Suche.

Angenommen ich hab folgenden <Float,Object> Baum
10.3f,x
15.5f,y
20.5f,z

Dann soll mir die Suche nach 11.0 x liefern
und die Suche nach 14 y

Geht sowas?
Kann mich erinnern dass es in der STL unter C++ sowas gab... aber hab nich so den plan von Java.
Danke in voraus.

 

[Klein0r]

Liegen die Daten denn sortiert vor?

 

[Sovok]

Ja die Daten sind sortiert.
Ich denk die beste möglichkeit ist mit arrays + binarySearch zu arbeiten und dann den Rückgabewert zu verwenden falls kein exakter match gefunden wird.

 

[Thomas Darimont]

Hallo,

schau doch mal hier:

package de.tutorials;

import java.util.Arrays;
import java.util.Comparator;

public class FindNearestElementExample {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Double[] values = { 20.0, 12.1, 123.321, 123.001, 123.002, 295.3, 12.4,	100.0 };
		Arrays.sort(values);
		System.out.println(Arrays.toString(values));

		int index = findIn(values, 123.321);
		System.out.println(index + " " + values[index]);

		index = findIn(values, 12.3, 0.1);
		System.out.println(index + " " + values[index]);

		index = findIn(values, 123.0, 0.0011);
		System.out.println(index + " " + values[index]);
		
		index = findIn(values, 21, 1.0);
		System.out.println(index + " " + values[index]);
	}

	private static int findIn(Double[] values, double value) {
		return Arrays.binarySearch(values, value);
	}

	private static int findIn(Double[] values, double value, double tolerance) {
		return Arrays.binarySearch(values, value, new ToleranceAwareComparator(tolerance));
	}
	
	static class ToleranceAwareComparator implements Comparator<Double> {
		double tolerance;

		public ToleranceAwareComparator(double tolerance) {
			this.tolerance = tolerance;
		}
		
		public int compare(Double o1, Double o2) {
			double delta = o1 - o2;
			if(Math.abs(delta) <= tolerance){
				return 0;
			}
			return (int)Math.signum(delta);
		}
	};
}

Ausgabe:

[12.1, 12.4, 20.0, 100.0, 123.001, 123.002, 123.321, 295.3]
6 123.321
1 12.4
4 123.001
2 20.0

Gruß Tom

 

[takidoso]

Hi Tom,
DieIdee mit der Toleranz ist ein echt interessanter Ansatz....

Aber mal eine Frage, was macht Dein Programm wenn es keine Zahl in der gewünschten Toleranz findet, oder das erste Element in der toleranz ist aber ein zweites noch besser passt weil Unterschied kleiner?

Müsste man nicht eigentlich drei Werte miteinander vergleichen (tatsächlicher Wert, höherer Wert und niedriger Wert) und den nehmen, der tatsächlich den kleinsten Unterschied bedeutet?