算法笔记_二分查找/斐波那契查找

谁借莪１个温暖的怀抱￠ 2023-02-18 09:56 84阅读 0赞

# 1. 查找 #

问题定义：在非降序数组中，找出指定的元素，如从\{1,2,3,6,8,12\}中找出元素2的位置。

二分查找的复杂度（比较次数，又称查找长度）是**O(1.5log(n))**，但不是最优的。改进：fibonacci数列进行改进。

原因：对于一个非降序数组，二分查找向左查找。需要比较1次，而向右查找，需要比较2次，存在不平衡，而我们希望，正确的比较（向左查找）的次数多一些，所以，不再使用从中间元素分成两半，进行查找，而是以fibonacci数列的值（1、1、2、3、5、8、13、21、34）作为划分数组的依据。如假设待查找数组的长度是21-1=20，第一次二分的点是13-1=12的位置，依次类推。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70][]

# 2. 例子 #

分别计算成功命中/未命中的查找次数，向左走，比较1次；向右走，比较2次。算得查找长度比二分查找略小（4.00<4.14）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 1][]

# 3 代码实现 #

与二分查找，唯一的不同在于分割点 middle point 取的是fibonacci数列中的点（黄金分割点，又叫轴点）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 2][]

# 4 推广与证明 #

二分查找与fibonacci数列查找的区别，在于分割点的选择上，我们将其设为λ，则查找的复杂度为 a(λ)log(n) 列出递推式，求解关于λ的系数函数a(λ)，使其最小，可证明正好当λ=0.618是，a(λ)最小，即最优复杂度为**1.44log(n)**.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 3][]

# 5 改进 #

为了使左右对比的次数都为1，所以稍微改变对比的规则，和终止的条件。当待查找的数值小于中间索引的数值时，划分区间，左侧没变化， 右侧，将中间数值也囊括进去。这样，终止条件就成了，上限索引比下限索引小1时终止。

改进的特点在于： 最好情况变坏，最坏情况有所变好，整体性能趋于稳定。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 4][]

hereto p65 [https://www.bilibili.com/video/BV1hJ411S7wU?p=65][https_www.bilibili.com_video_BV1hJ411S7wU_p_65]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617133444516.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200617134701964.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200617135517438.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200617140211765.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200619200929261.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ==,size_16,color_FFFFFF,t_70
[https_www.bilibili.com_video_BV1hJ411S7wU_p_65]: https://www.bilibili.com/video/BV1hJ411S7wU?p=65