当前课程知识点:Data Structures and Algorithm Design Part I > 02.Vector II > D3.Sorted_Vector.fibonaccian_search > 02D3-2
返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part I》慕课在线视频列表
fibonacci查找
大致可以实现为这样一段代码
可以注意到
它的接口还是完全一样的
而且在其中的这个循环
大致来说,也是类似地
具体来说,每次我们都要来判断
以保证当前的lo和hi
构成一个合法的区间
如果有朝一日,
这个区间能够收缩到非法
那也就意味着,查找是失败的
这个跟我们此前的版本A是一样的
那么在内部呢
最重要的是要来确定
当前的这个mi
也就是这个pivot,这个轴点
按照此前所说的算法
我们每次都要取出来fibonacci数的下一项
然后把这个数减1
所以大家可以看到
在这里我们有一个fibonacci类
这个类呢,提供一个接口
使得我们能够不断地取它的前一项
当然还有我们这里没有用到
实际上也提供了的
它的后继一项
无论如何,它总能返回
恰好是前面一个适当的一个项
这个项就是刚才我们说的那个切分点
以这样的一个切分点来切分
此后的这三句和我们此前所讲过的
二分查找别无二致,完全一样
所以我们也可以看出来
所谓的fibonacci search
和binary search的区别
并不在于算法的这个大体的策略
其实本质上讲只在于
这个pivot,也就这个middle point
是怎么取的
如果是按平均来取,就是binary search
如果是按照刚才所说的黄金分割点来取
那么就是fibonacci search
-A.Computation
--01A-1
--01A-2
--01A-3
--01A-4
--01A-5
--演示
--01A-6
--(a)计算--作业
-B.Computational_Models
--01B-1
--01B-2
--01B-3
--01B-4
--01B-5
--01B-6
--01B-7
--01B-8
-B.Computational_Models--Homework
-C.Big_o
--01C-1
--01C-2
--01C-3
--01C-4
--01C-5
--01C-6
--01C-7
-C.Big_o--Homework
-D.Algorithm_analysis
--01D-1
--01D-2
--01D-3
--01D-4
--01D-5
--01D-6
--01D-7
-D.Algorithm_analysis--Homework
-E.Iteration+Recursion
--01E-1
--01E-2
--01E-3
--01E-4
--01E-5
--01E-6
--01E-7
--01E-8
--01E-09
-E.Iteration+Recursion--Homework
-F.Dynamic_Programming
--01XC-1
--01XC-2
--01XC-3
--01XC-4
--01XC-5
--01XC-6
-- 演示
--01XC-7
--01XC-8
--01XC-9
--01XC-A
-F.Dynamic_Programming--Homework
-Homework
-A.Interface+Implementation
--02A-1
--02A-2
--02A-3
--02A-4
--02A-5
-A.Interface+Implementation--Homework
-B.extendable_vector
--02B-1
--02B-2
--02B-3
--02B-4
--02B-5
-B.extendable_vector--Homework
-C.unsorted_Vector
--02C-1
--02C-2
--02C-3
--02C-4
--02C-5
--02C-6
--02C-7
--02C-8
-C.unsorted_Vector--Homework
-D1.Sorted_Vector.uniquify
--02D1-1
--02D1-2
--02D1-3
--02D1-4
--02D1-5
-D1.Sorted_Vector.uniquify--Homework
-D2.Sorted_Vector.binary_search
--02D2-1
--02D2-2
--02D2-3
--02D2-4
--02D2-5
--02D2-6
--02D2-7
-D2.Sorted_Vector.binary_search--Homework
-D3.Sorted_Vector.fibonaccian_search
--02D3-1
--02D3-2
--02D3-3
--02D3-4
-D3.Sorted_Vector.fibonaccian_search--Homework
-D4.Sorted_Vector.binary_search_optimized
--02D4-1
--02D4-2
--02D4-3
--02D4-4
--02D4-5
-D4.Sorted_Vector.binary_search_optimized--Homework
-D5.Sorted_Vector.interpolation_search
--02D5-1
--02D5-2
--02D5-3
--02D5-4
--02D5-5
-D5.Sorted_Vector.interpolation_search--Homework
-E.Bubblesort
--02 E-1
--02E-2
--02E-3
--02E-4
--02E-5
-E.Bubblesort--Homework
-F.Mergesort
--02F-1
--02F-2
--02F-3
--02F-4
--02F-5
--02F-6
-F.Mergesort-Homework
-Homework
-A.interface+Implementation
--03A-1
--03A-2
--03A-3
--03A-4
-A.interface+Implementation--Homework
-B.Unsorted_list
--03B-1
--03B-2
--03B-3
--03B-4
--03B-5
-B.Unsorted_list--Homewrok
-C.Sorted_list
--03C-1
--03C-2
--03C-3
-C.Sorted_list--Homewrok
-D.Selectionsort
--03D-1
--03D-2
--03D-3
--03D-4
--03D-5
--03D-6
-D.Selectionsort--Homework
-E.Insertionsort
--03E-1
--03E-2
--03E-3
--03E-4
--03E-5
--03E-6
--03E-7
--03E-8
-E.Insertionsort--Homework
-(xd):LightHouse
--03XD
-Homework
-A.stack-ADT+implementation
--04A-1
--04A-2
--04A-3
-A.stack-ADT+implementation--Homework
-C1.stack-App-conversion
--04C1-1
--04C1-2
--04C1-3
-C1.stack-App-conversion--Homework
-C2.stack-App-parentheses
--04C2-1
--04C2-2
--04C2-3
--04C2-4
--04C2-5
--04C2-6
-C2.stack-App-parentheses--Homewrok
-C3.stack-App-permutation
--04C3-1
--04C3-2
--04C3-3
--04C3-4
--04C3-5
-C3.stack-App-permutation--Homework
-C4.stack-App-infix
--04C4-1
--04C4-2
--04C4-3
--04C4-4
--04C4-5
--04C4−6A
--04C4−6B
--04C4−6C
--04C4-6D
-C4.stack-App-infix--Homework
-C5.stack-App-rpn
--04C5-1
--04C5-2
--04C5-3
--04C5-4
-C5.stack-App-rpn--Homework
-D.Queue-ADT+implementation
--04D-1
--04D-2
--04D-3
-Homework
-A.Tree
--05A-1
--05A-2
--05A-3
--05A-4
--05A-5
--05A-6
--05A-7
-A.Tree--Homework
-B.Representation
--05B-1
--05B-2
--05B-3
--05B-4
--05B-5
-B.Representation--Homework
-C.Binary_Tree
--05C-1
--05C-2
--05C-3
-C.Binary_Tree--Homework
-D.Implementation
--05D-1
--05D-2
--05D-3
--05D-4
--05D-5
-D.Implementation--Homework
-E1.Preorder
--05E1-1
--05E1-2
--05E1-3
--05E1-4
--05E1-5
--05E1-6
--05E1-7
--05E1-8
--05E1-9
-E1.Preorder--Homework
-E2.Inorder
--05E2-1
--05E2-2
--05E2-3
--05E2-4
--05E2-5
--05E2-6
--05E2-7
-E2.Inorder--Homework
-E4.LevelOrder
--05E4-1
--05E4-2
--05E4-3
-E4.LevelOrder--Homework
-E5.reconstruction
--05E5-1
--05E5-2
--05E5-3
-E5.reconstruction--Homework
-Homework
-A.Introduction
--06A-1
--06A-2
--06A-3
-A.Introduction--Homework
-B1.Adjacency_Matrix
--06B1-1
--06B1-2
--06B1-3
--06B1-4
--06B1-5
--06B1-6
--06B1-7
--06B1-8
--06B1-9
-B1.Adjacency_Matrix--Homework
-C.BFS
--06C-1
--06C-2
--06C-3
--06C-4
--06C-5
--06C-6
--06C-7
--06C-8
-C.BFS--Homework
-D.DFS
--06D-1
--06D-2
--06D-3
--06D-4
--06D-5
--06D-6
--06D-7
-D.DFS--Homework
-Homework