当前位置:网站首页>fibonacci search
fibonacci search
2022-07-05 22:47:00 【Brother Yu...】
Introduction of Fibonacci search
Two point search is familiar to everyone , Every time 1/2 Fold check , Then someone thought , If you don't follow 1/2 If you check , Will it be more efficient in some cases ? So someone thought 0.618( The golden section ), But using this decimal directly is a little less elegant . At this time, people think of Fibonacci series .
1 1 2 3 5 8 13 21 34 55 89…… We will find that as the Fibonacci sequence increases , The ratio of the two numbers will be closer and closer 0.618, Take advantage of this feature , We can apply the golden ratio to the search technology .
The basic idea
By using the concept of golden ratio, select the search point in the sequence to find , Improve search efficiency . similarly , Fibonacci search also belongs to an ordered search algorithm .
The total length of the array is F[K]-1,mid The front length is F[K-1]-1, The back length is F[K-2]-1,mid At the golden section .
Algorithm implementation
public class Fibonacci {
public static void main(String[] args) {
int[] arr = {
1, 8, 10, 89, 1000, 1234};
System.out.println(fibSearch(arr , 99));
}
public static int maxSize = 20;
public static int[] fib() {
int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for(int i = 2; i < maxSize; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
// Fibonacci looks for ( In fact, it is the point of each search , Are close to dividing the array into 0.618 ratio , Number of elements on the left / The total number of elements About equal to 0.618)
// I want to search by ( Find the element on the left of the point / The total number of elements ) near 0.618 Get the index of the search element .
// Because Fibonacci looked , The ratio of two adjacent items is close 0.618, Then it is used in the search algorithm according to the law of Fibonacci sequence .
public static int fibSearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;
// A subscript representing the Fibonacci division value
int k = 0;
int mid = 0;
int f[] = fib();
// Get the Fibonacci partition value subscript , According to the length of the lookup array , Decide how many Fibonacci values are needed
while(high > f[k] - 1) {
k++;
}
// because f[k] The value may be greater than a The length of , So we need to use Arrays class , Construct a new array , And point to a[]
// The insufficient part will be used 0 fill
int[] temp = Arrays.copyOf(a, f[k]);
// In fact, you need to use a The last number of the array is filled temp
// for example :temp = {1,8,10,89,1000,1234,0,0,0} => {1,8,10,89,1000,1234,1234,1234}
for(int i = high + 1; i < temp.length; i++) {
temp[i] = a[high];
}
// Use while To cycle through , Find our number key
while(low <= high) {
mid = low + f[k - 1] - 1;
// We should continue to look to the left of the array
if(key < temp[mid]) {
high = mid - 1;
// Why k--
// All elements = The front element + Back element f[k] = f[k - 1] + f[k - 2]
// Because there are f[k - 1] Elements , So we can continue to split f[k - 1] = f[k - 2] + f[k - 3]
// That is to say f[k - 1] Left continue to search k--, Next cycle mid = f[k - 1 - 1] - 1
k--;
} else if(key > temp[mid]) {
// All elements = The front element + Back element f[k] = f[k - 1] + f[k - 2]
// Look on the right
low = mid + 1;
k -= 2;
} else {
return Math.min(mid, high);
}
}
return -1;
}
}
边栏推荐
- Wonderful review of the digital Expo | highlight scientific research strength, and Zhongchuang computing power won the digital influence enterprise award
- How can easycvr cluster deployment solve the massive video access and concurrency requirements in the project?
- Solve the problem of "no input file specified" when ThinkPHP starts
- 50. Pow(x, n). O(logN) Sol
- Paddle Serving v0.9.0 重磅发布多机多卡分布式推理框架
- The countdown to the launch of metaverse ape is hot
- Kubernetes Administrator certification (CKA) exam notes (IV)
- Global and Chinese markets of industrial pH meters 2022-2028: Research Report on technology, participants, trends, market size and share
- Navigation day answer applet: preliminary competition of navigation knowledge competition
- Opencv judgment points are inside and outside the polygon
猜你喜欢
第一讲:蛇形矩阵
d3dx9_ What if 29.dll is missing? System missing d3dx9_ Solution of 29.dll file
Practice: fabric user certificate revocation operation process
谷歌地图案例
Sparse array [matrix]
Golang writes the opening chapter of selenium framework
实战:fabric 用户证书吊销操作流程
Navigation day answer applet: preliminary competition of navigation knowledge competition
点到直线的距离直线的交点及夹角
航海日答题小程序之航海知识竞赛初赛
随机推荐
Nacos 的安装与服务的注册
[groovy] groovy dynamic language features (automatic type inference of function arguments in groovy | precautions for function dynamic parameters)
Codeforces Global Round 19
3 find the greatest common divisor and the least common multiple
Double pointer of linked list (fast and slow pointer, sequential pointer, head and tail pointer)
第一讲:蛇形矩阵
Solve the problem of "no input file specified" when ThinkPHP starts
2022软件测试工程师涨薪攻略,3年如何达到30K
MCU case -int0 and INT1 interrupt count
Global and Chinese markets of tantalum heat exchangers 2022-2028: Research Report on technology, participants, trends, market size and share
BFC block level formatting context
GWT module may need to be (RE) compiled reduce - GWT module may need to be (RE) compiled reduce
从 1.5 开始搭建一个微服务框架——日志追踪 traceId
Metasploit(msf)利用ms17_010(永恒之蓝)出现Encoding::UndefinedConversionError问题
我对新中台模型的一些经验思考总结
南京:全面启用商品房买卖电子合同
Binary tree (III) -- heap sort optimization, top k problem
[error record] groovy function parameter dynamic type error (guess: groovy.lang.missingmethodexception: no signature of method)
Metasploit (MSF) uses MS17_ 010 (eternal blue) encoding:: undefined conversionerror problem
Assign the output of a command to a variable [repeat] - assigning the output of a command to a variable [duplicate]