Loading…
Loading…
Narrows the range by Fibonacci numbers instead of halves, so every probe is computed with additions only — no division.
n = 15, so the smallest Fibonacci number that covers it is 21. Every probe from here on is offset + a Fibonacci number — additions only, never a division.
Tip: click any bar to make it the target.
1int fibonacciSearch(int[] a, int target) {2 int n = a.length, f2 = 0, f1 = 1, f = 1;3 while (f < n) { f2 = f1; f1 = f; f = f1 + f2; }4 int offset = -1;5 while (f > 1) {6 int i = Math.min(offset + f2, n - 1); // no division — Fibonacci steps are pure additions7 if (a[i] < target) { offset = i; f = f1; f1 = f2; f2 = f - f1; }8 else if (a[i] > target) { f = f2; f1 = f1 - f2; f2 = f - f1; }9 else return i;10 }11 if (f1 == 1 && a[offset + 1] == target) return offset + 1;12 return -1;13}