Đang tải…
Đang tải…
Thu hẹp khoảng theo các số Fibonacci thay vì chia đôi, nên mọi điểm dò chỉ cần phép cộng — không có phép chia.
n = 15, nên số Fibonacci nhỏ nhất phủ được nó là 21. Mọi điểm dò từ đây là offset + một số Fibonacci — chỉ có phép cộng, không hề có phép chia.
Mẹo: bấm vào một cột để chọn nó làm mục tiêu.
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); // không có phép chia — các bậc Fibonacci chỉ là phép cộng7 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}