02D4-1慕课视频播放-Data Structures and Algorithm Design Part I-MOOC慕课视频教程-柠檬大学

欢迎同学们回来

我们这一节继续讨论有序向量查找算法的改进

回顾上节，我们所介绍的fibonaccian search

实际上，它的改进思路是在注意到

我们查找的过程中的每一步

向左和向右深入的成本是不一样的

具体来说，左边是1的话，右边就是2

所以它试图做这样一个改进

使得整个搜索的倾向

更加地偏向于成本更低的左侧

而使得向右的分支，出现的概率更低

这样的话，我们也严格证明了

在总体情况下

它的查找性能将会得到改进

甚至从一般的意义上讲，已经是最优的了

那么我们这一节呢

将给大家介绍另一种思路的改进

这是一种直截了当的改进思路

既然我们已经注意到了

此前的版本A中

造成效率略低的原因是因为

左右分支的转向代价不平衡

那么我们为什么

就不能够将二者做成是平衡的呢？

也就是说，如果在任何一个位置

我们需要向左和向右的话

我们希望能够使得无论是向左还是向右

只需要进行一次比较

没错，一次比较

当然这样的话，我们每一次迭代中

经过一次比较之后

就只能有两个分支而不是像以前一样

实际上是三个

也就是说，原来隐藏了一个分支

那么原来版本A隐藏的是哪个分支呢？

大家应该能想得到

也就是在当前这个轴点处

命中的那个分支

我们说这个分支，某种意义上讲是

更好甚至是最好的情况

因为在这个时候，我们就可以直接返回了

而在我们采用了新的这样一个改进思路以后

为了获得在每一处的平衡

我们不得不在这个位置上做出一点牺牲

具体来说，我们同样地还是以

中点mi作为轴点

只不过呢，只进行一次判断

也就是我们只判断

我们的目标关键码是否是

严格地小于当前的轴点

如果它确实是小于轴点

那么我们就向左侧区间深入

反过来，如果刚才那句判断答案是否

也就是说，e是大于等于当前的这个轴点x

那么我们就可以断定

它如果存在的话

必然位于右侧的子区间

同样可以进行递归地深入

大家注意，这里头的细微区别

虽然我们这里依然用左和右来区分

两种减而治之的可能和方向

而且左侧的也确实和以前的没有任何区别

但是右侧这个分支所对应的子向量

却略有区别

这个区别就在于

它将这个轴点同时也涵盖进去了

换而言之，正像我们刚才所说的

在这个时候，必须做出一个牺牲

也就是说，我们不能够及时地判定

在当前这个位置已经命中

正如我们马上就要看到的

新的这个算法必须等到整个这个区间

经过足够多次减而治之

最后的区间宽度变成1的时候

才会真正地去判断

当前唯一的这个元素是否是真正命中的

这也就是新的这个算法和此前的算法

在策略上的不同

但是无论如何，这确实是可行的

因为它已经使得我们在任何一个细微处

都能够做到理想的平衡

所以从而使得整个问题更加地简化

Data Structures and Algorithm Design Part I课程列表：

01.Introduction I

-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

01.Introduction II

-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

02.Vector I

-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

02.Vector II

-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

03.List

-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

04.Stack+Queue

-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

05.Binary_Tree

-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

06.Graph

-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

02D4-1在线视频

02D4-1课程教案、知识点、字幕

Data Structures and Algorithm Design Part I课程列表：

01.Introduction I

01.Introduction II

02.Vector I

02.Vector II

03.List

04.Stack+Queue

05.Binary_Tree

06.Graph

02D4-1笔记与讨论

也许你还感兴趣的课程: