Effizientere Suche bei bekannter Verteilung (hier linear)
In diesem Beispiel gehen wir davon aus, dass die Werte im Wesentlichen linear verteilt sind. Das bedeutet, dass die Differenz zwischen zwei aufeinanderfolgenden Werten immer gleich ist.
Sei beispielsweise ein Array a mit folgenden Werten geben (Auszug):
Index i |
Wert |
|---|---|
i = 10 |
a[i = 10] = 20.0 |
... |
... |
i = 30 |
49.5 |
... |
... |
i = 50 |
87.2 |
... |
... |
i = 70 |
151.3 |
... |
... |
i = 90 |
169.9 |
... |
... |
i = 110 |
220.0 |
... |
... |
i = 130 |
251.2 |
Wenn man jetzt exemplarisch die Paare: \((i = 10, a[i] = 20.0)\), und \((i = 110, a[i] = 220)\) betrachtet, dann kann man zu dem Schluss kommen, dass die Funktion \(f(x) = 2.0\cdot x\) eine Approximation der Verteilung der Werte ist. Würde man also nach dem Wert \(a[i] = y = 170\) suchen wollen, dann wäre es gut als erstes den Wert von a[85] zu überprüfen, \(170 = 2\cdot x \rightarrow \frac{170} {2} = 85 = i\).
