当前课程知识点:Data Structures and Algorithm Design Part I >  02.Vector I >  D2.Sorted_Vector.binary_search >  02D2-3

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

02D2-3在线视频

下一节:02D2-4

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

02D2-3课程教案、知识点、字幕

这种在语义上进一步地细致约定

是非常有必要的

否则的话,我们的search接口

将只能作为一个孤立的功能

而不能有效地、便捷地

为其它的算法,作为一个基本的部件而利用

比如说,search接口至少应该

使得有序向量自身的动态维护变得非常便利

比如说,在有序向量不断插入元素过程中

我们希望往往能够采用这样一种形式

也就是说,当我们需要

去插入某一个元素的时候

我们首先要通过search

来确定一个适当的位置

比如说,就是这个查找返回的那个值再加1

然后再将e插入于这样一个秩所对应位置

并且同时使得这个有序向量

继续是一个有序向量

所以这样的话

对我们刚才所说的几种特殊情况

就有明确的要求

而不是说可以简单地处理

比如说,即便是失败

我们也需要给出新元素插入的适当的位置

也就是说,我即使跌倒了,我也不能白白跌倒

我应该为后继者提供一个参考的依据

反过来,即便是有重复的元素

比如说像刚才所说的

在这个地方,可能有多个元素

构成一个区段

它们都是某一个特定的元素

我也需要使得新插入的元素

总是,比如说,排在最后或者是排在最前

这样的话呢

能够使得每一组这样的元素

排列的相对次序

与它们的插入的次序是吻合的

那么这些呢,都是属于语义方面的

更深入的要求

很幸运,前人已经帮我们设计出了

这样的语义约定

比如说,这就是其中的一种

我们这里约定

search接口的返回值总可以概括地

说是不大于目标的最后那个元素

确切地讲,是它的秩

我们来看几种特殊的情况

第一种情况,就是查找失败

如果查找失败,按照这里的约定

它会失败在

一个不大于这个e的最大的那个元素

所以如果随后的这个元素是存在的

它必然是大于e的

而这边这个呢,必然是小于等于e的

所以如果返回值是在这

我们将新的那个元素插入在

它的位置再加1的这个位置上

那么是再合适不过的了

其实这里头也有几种特殊的情况

比如说,这个元素确实不存在

但是它的数值非常非常的小

以致于这个区间内,最左侧最小的这个元素lo

也比它大

这个时候有效范围内的任何元素

都是不能作为返回值返回的

这时候我们返回什么呢?

我们倾向于返回lo-1

因为这样的话

如果我们接下来确实要把这个元素插入进来

那么也就是插入在lo这个位置上

这个和我们的要求是吻合的

那么怎么做到这一点呢?

我们说,以假想地在lo的左侧

就像现在这样,再增加一个哨兵

而它的数值呢

我们可以等效地认为,是等于负无穷

反过来,如果

待插入的这个元素e非常非常大

以致于连实际存在的这个

最大的这个hi-1也要比它严格地小

那么这个时候呢

如果要插入的话,应该插入在hi这个位置

这个虚拟的

有可能根本不存在的这样的一个位置上

那么这个时候

返回的值应该是hi-1

再合适不过了

因为如果是hi-1是作为返回值的话

那么把这个数值插在hi这个位置上

和我们的功能也是吻合的

所以对称地

我们不妨认为这个假想的哨兵hi

所具有的数值也是有的

只不过它是正无穷

所以这种情况不仅能处理

而且可以有一个很好的一个解释

再来看,重复元素的情况

如果确实像刚才所言,在这个地方

可能有多个元素是与目标的元素是重复的

这个时候呢

我们说这个算法按照这里的要求

应该返回的所谓的不大于e的最后一个元素

当然也就是这个区段的右端点了

所以接下来,如果我们要做一个插入

也就是说

把这个位置同样地加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

02D2-3笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。