大家好！ Hello everybody!
数据结构与算法这一讲的内容我们继续第十章检索的学习。 For the content of the data structure and algorithms of this lecture, we continue to study the tenth chapter retrieval.
今天我们的内容主要是基于线性表的检索方法。 Today our content is the retrieval method based on the linear table.
我们介绍顺序检索，二分检索，和分块检索，这三种方法。 We introduce these three methods of sequential search, binary search and blocking retrieval.
顺序检索是对无序的线性表进行的。 Sequential search is for a linear disordered table.
我们只能逐个检索这个记录里面的所有关键码。 Then we can only retrieve all the key codes in the records.
挨个比较。 Compare one by one.
如果能够成功地检到这个记录，我们就，返回相应的下标位置。 If you can successfully check the record, we will return the corresponding index position.
如果比较完了整个线性表，还没有找到跟给定的这个关键码值相等的这么一个元素， 我们就是检索失败。 If comparing over the entire linear table, you have not found with such an element equal to the given key value, We fail to retrieve it.
顺序表的检索方法，我们不需要排序。而且它适合于顺序表和链表的这两种存储方法。 For retrieval methods of sequence table, we don't need to sort. And it is suitable for the sequence table and chain table.
我们来看一下顺序检索的这个算法。 Then we take a look at the algorithm of sequential search.
这个算法里面，我们有个特殊的处理就是，对于这个顺序表里面，下标0的这个位置，我们不存储整个有效的元素。 In the algorithm, we have a special treatment is, in this sequence table, the subscript 0 this position does not stored the whole effective element.
我们是用来存待检的这个key值。 Well, we use it to deposit the key values waiting for the test.
对整个这样的一个顺序表。 For such a sequence table.
我们从最右的下标往前来逐个比较。 We compare one by one from the most right subscript forward.
如果是找到了这样的一个跟我们指定的K相等的这么一个关键码， 我们就返回它相应的一个下标位置i。 If finding the key equal to a specified K, we will return the corresponding subscript position I.
如果是一直找，都没找到的话，它必然停在这个下标0的位置， if we don't find it, it must stop at the position of the subscript 0,
跟我们前面的这个，设定的这个待检的k，是相等的。 equal to the K before.
我们就返回这个下标0，表示检索失败。 Then we will return the subscript 0, meaning retrieval failure.
我们来看一下， 顺序检索它的性能。 we take a look at the performance of sequential search.
假设每一个关键码它是以n分之1的等概率来发生检索的。 Suppose that every key is retrieved by 1/n probability.
这样的话我们在整个这个线性表里面，我们最后个元素可能是只能比较一次就能够检索出来。 That, if so, in the whole linear table, the final element May be retrieved by comparing once.
排在这个顺序表里面最前面的个元素，它是要比较n次才能够找到它。 The front element in the sequence table needs being compared n times to find it.
因此，它的一个平均检索长度，就是这么一个公式。 It, therefore, the average retrieval length is such a formula.
我们得到的这个值，就是2分之n加1。 So, the value is (n+ 1) /2.
失败检索一定是落到我们这个数组下标0位置，才能够判断说一个失败。 The failure to retrieve must be landed on the array subscript zero position, and then we can say the judge is a failure.
所以我们是n加1次。 So n + 1 times.
如果是说，成功检索的概率是P，然后失败检索的概率是Q， 而且，P加Q等于1。 If the probability of successful retrieval is P, and the probability of failure to retrieve is Q, And yet, P and Q is equal to 1.
我们可以看到它的平均检索长度就是， P乘以2分之n加1，加上Q乘以n加1。这个值它是处于2分之n加1，到n加1之间。这是一个Theta n量级的。 We can see that the average length of retrieval is P multiplied by (n + 1)/2 plus Q multiplied by n + 1. the value, it is in (n + 1)/2 between n + 1. This is a Theta N order of magnitude.
顺序比较的优点是，我们插入元素的时候可以直接插在末尾。 但是，它的检索长度太长了，是Theta n量级的。 The sequence comparison, its advantage is that elements we insert can be directly inserted in the end. But, its retrieval length is too long, is Theta N order of magnitude.
因此我们考虑采用更高效的检索方法。 So we consider adopting more efficient retrieval method.
首先，我们要对待检的这些元素进行一下排序。 First of all, we sort the elements.
排完序以后，我们就可以采用二分检索的方法了。 Then we can adopt the method of binary search.
二分检索是可以像我们查字典样，就是我待检的这个k，跟整个顺序表里面的中间的个元素进行相比。 The binary search can be like looking up dictionary, that is, compare k, with the central element in the entire sequence table.
如果是等，就检索成功。 If equal, it is retrieved successfully.
如果是说中间个Key大于我们待检的值，我就会是在左半边继续比较。 If the middle Key is more than the value we are going to retrieve, I continue to compare on the left side.
如果中间Key小于我们待检的这个K，就在右半边继续比较。 If the Key is less than the K, I will compare in the right half.
每一次，我们都会缩小这样几乎一半的待检的区域规模。 Every time we will narrow it to almost half of the area.
不断的缩小，我们就很快地能够达到目标的一个下个位置。 By constantly narrowing, we will soon be able to reach a place in the next of such a goal.
我们，看下二分检索算法它的框架。 Then we look at the binary search algorithm, its framework.
为了跟前面这样的顺序检索保持一致，这个下标0内也是不存放具体的元素的。 in order to follow the front order retrieval，the subscript 0 is not stored within the specific elements.
我们这样的一个左下标low，就从1开始。 Such a left subscript low, starts from 1.
右下标这个high，就是整个这个长度length个位置。 This high, right subscript is the position of the whole length.
然后，我们在这个low和high，它所界定的区域是有效的时候， 我们一直进行这个循环。 Then, the low and high, when the area it defined is effective, We have been in the loop.
首先我们取出它们的这个中间位置的这个下标。 At first we remove the subscript in the middle position.
这里是low加high除2，然后取得下整。 Then, divide the sum of low and high by 2, and take the integer.
然后我们看一下，这个待检的key它跟中间这个mid数值的大小。如果k小于这个mid所在的这个位置的值， 我们需要 把high往左边推进。我们是在整个区域左半部分继续进行。 Then we compare the key and middle. if the k is less than the value of the mid of the location, We need to push the high on the left. We continue in the left of the whole area.
否则，如果，key，大于我们mid所在的这个位置， 我们就是，low，往这个右半部分来推进。 otherwise, if key is greater than mid in this position, we advance low to the right side.
相当于在右半部分继续来检索。 That is equivalent to retrieving in the right side.
如果是相等，就检到了。 If it is equal, we retrieve it successfully.
我们继续这个循环。 如果是这个区域已经是无效的，我们还没有检到,就会是，返回这个0位置。 这个0就跟我们前面的顺序检索保持一致。 Then we continue the cycle. If this region is invalid, we haven't checked it, we will return to the zero position. The 0 is consistent with our previous order.
我们来看一下这个顺序检索的这个图示。 low和high这样的，就是左下标和右下标，这样的一个区域。 我们来看这个，它的中间就是在这个下标5的这个位置。然后我们待检的元素是18。 18比35要小，这个区域缩小到左半部分进行。 we take a look at this graphic of sequential search. low and high is such an area ofleft subscript And right subscript. the middle of it is this position of the subscript 5. inspection of element is 18. The 18 is smaller than 35, so this area is narrowed to the left.
然后，在左半部分里面，这个中间位置是下标2，然后这个值是17。 17，比18要小，所以，我们又在这个区域的右半部分进行，然后一直到找到18这个值。 And then, inside the left half, the middle position is the subscript 2, and the value is 17. 17 is smaller than 18, so, we search in the Right side, and find this value.
我们看一下这个二分检索的性能。 首先，二分检索的过程，它其实是，由这样的一个待检数组，它所决定的一个，决策树的一个过程。 这个决策树，它其实是一个BST。 We take a look at this binary search performance. First of all, well, the process of binary search, it actually is such a process of decision tree determined by an array of waiting for inspection. the decision tree, it is actually a BST.
我们每次从这个中间的位置二分地下来。 然后，形成了这么一个BST。 这个BST的结构，主要是跟我们整个这个数组的元素个数，以及，我们在划分的时候是取上整还是取下整，来取这个中间的下标位相关。 跟这个待检数组里面的，它的具体的元素值无关。 跟我们待检的关键码值，是更没有关系了。 every time we do from the middle position binaurally. Then, form the BST. The structure of this BST is related to The number of elements in the array, and, whether top integer or bottom integer to take the middle subscript. It has nothing to do with its specific element value in the inspected array. the key value is also no relationship.
我们，可以看到这么一个决策树。 它的这个最大长度，就是在这个最底层的这个叶节点的位置。 它的这个失败的检索长度，就是最底层这个叶节点，以及倒数第二层的检索位置。 它的失败检索长度，也是log n量级的。 Then you can see such a decision tree. the largest length is in the bottom of the leaf node location. the failure to retrieve the length Is the bottom of the leaf node, and the second from bottom of retrieval. the length failing to retrieve is also the log n order of magnitude.
在算法复杂度里面，我们往往是以这个，log n，来表示整个这样的一系列的， 这些算法的复杂度。 我们这里，很多情况下以2为底，但是其他的数值为底的话我们可以通过换底公式来得到这么一个就是以log2为底的这么一个带常数的某一个这样的量级。 in the algorithm complexity, we often use the log N, to represent the complexity of the whole series of the algorithm. in many cases we use 2 as the base, but for the other numerical we get the magnitude of log2 by changing the base.
但是，因为我们算法复杂度里面，我们并不关心这些前面的系数，和后面的一些低维度的量级， 因此，它的算法量级是不变的。 Because in the complexity of our algorithm, we don't care the front coefficients and behind magnitude of low dimension, the algorithm is the same magnitude.
二分检索它的一个平均检索长度，在这里，我们，可以观察这个决策树。 在根这个位置只有一个元素，它的比较次数是1。 Then we binaurally retrieve the average length of retrieval. Here, we can take a look at this decision tree. in Root there is only one element, and the compare number is 1.
然后，第2层，就是根底下的这个，这一层有两个元素，它的比较次数都是2。然后再依次往下推，一直到这个叶节点层。我们可以看到，这个平均检索长度，大概会是这么一个值，它就是大约是等于log以2为底， 然后（n+1）的对数再减1，比我们刚才的个最长的检索长度可能是小一次， Then, in the second Layer there are two elements, the comparison of its number are 2. And then we in turn push down until the leaf node layer. You can see, the average length of retrieval, probably would be, Such a value, it is equal to the log with 2 at the bottom, And then the logarithm of (n + 1) minus 1, smaller once than the longest length we just retrieve.
所以它的最大的这个检索长度和平均检索长度是接近的，都是log n的量级。 它的缺点就是，我们需要排序。而且，它的插入是非常不方便的。 so the maximum length of the retrieval is close to the average retrieval, they are the log n level. its disadvantage is that we need to sort. And, its insertion is very inconvenient.
因为我们在插入新元素的时候要保持它的这么一个有序性，就像插入排序样，我们找到这个位置。 这个位置之后的所有元素都要移动，大概会是平均情况下二分之n的元素都要移动。 Because we need to keep such an order When inserting the new element, that is, as insertion sort, we find this location. all the elements after this position need to move, it will probably be the average case is 1/2 n elements to move.
我们再来看一个分块检索。 Then we look at a retrieval.
分块检索它就是综合了我们顺序检索和二分检索它的优点。 The chunked retrieval comprehends the advantages of sequential retrieval and dichotomizing retrieval, which we have learnt.
我们首先是对这个线性表里面我们划分成若干个块儿，然后块儿跟块儿之间它是有序的，但是块儿内是没序的。 First, we put the space of linear table into several blocks, these blocks are sequential, while no sequence within any block.
这样的话我们在检索相应的块儿的时候，我们可以用二分检索的方法来找到这个对应块儿， Because of this, when we retrieve the corresponding block, we can use the method of dichotomizing retrieval to find it.
然后我们在这个块儿里面再去顺序查找， Then we retrieve the data which we need by using sequential retrieval.
这样的话，我们的这个检索的速度它相对来说比顺序检索要快不少，而它的这个插入的灵活性又比这个二分检索要好。 So the speed of chunked retrieval is much faster than sequential retrieval’s, and the flexibility of inserting is better than dichotomizing retrieval’s.
我们来看一下，这样的一个分块检索的例子。 Now I’ll show you an example of chunked retrieval. Let’s see it.
首先这个线性表我们分成若干块。 We put the space of this linear table into several blocks.
这个块他们之间是有序的，而块的内部是无序的。 All these blocks are sequential, while there is no sequence in the interior of any block.
我们对这个每一块我们都要建立索引信息，得到一个块索引表。 We need to define index information for every block, which create a block index table.
这个索引表里面最主要的就是，每一块里面最大的这个元素的它的一个关键码值 以及这个块里面它的起始的这个下标位置还有它的这个终止的下标位置其实也是需要记录的。 In this index table, the uppermost data is the key value of the maximal element in every block, as well as the subscript position of starting and termination within this block, all of them should be recorded.
当然我们可以记录这个块里面它的元素个数， 也是等效的。 While recording the number of elements in this block is equivalent.
还有，我们记录了这个块里面最大的关键码值，其实也不一定非要记录最大，我们相应的有一种方法是记录这个块里面最小的关键码值，也是可以的。 Besides, we can record the key value of the minimum element instead of the maximal one’s.
这样的话，我们对这么一个结构，我就可以在查找的时候是先从这样一个索引表里面去用二分的方法找这个相应的块， 然后在找到块里面以后我就从它的这个起始位置然后再逐个地去找。 Based on this structure, I can begin to retrieve with finding the corresponding block by dichotomizing retrieval within the index table, and then retrieve elements one by one from the starting position in this block.
看看是不是能找到我们待查的样的一个关键码值，它所在的这个记录的这些信息。 Then we’ll check if we can find the retrieved key value and information this key records.
在这个分块检索的这个结构里面，插入它就是一个失败检索。 In the structure of chunked retrieval, inserting an element would be a failed retrieval.
也就是说我们插入的时候，需要查找这个相应的关键码，看看它在整个这个线性表里面是不是存在。 That is we need to retrieve the corresponding key before inserting any element, and check if this key exists in the whole linear table.
如果是不存在我们可以插入，如果是说它存在的话其实对于我们这样的一个数据结构里面的这些索引的这些结构， 我们往往都不支持重复关键码的这样的信息。 If it doesn’t exist, we can insert an element; but if it exists, because of the chunked retrieval’s index structure, our computers always doesn’t support such information like repetitive key.
如果你非要支持的话，你就是自己去拉出一个链的这样的一个同义词链这样的结构。 While, if you insist on supporting repetitive key, you have to set a chain structure of synonymous.
我们看一下这个分块检索的性能。 Now we’ll check the function of chunked retrieval.
首先我们假设整个这个线性表分为b块，然后每一块里面的元素个数是s。 First, we assume that the whole space of the linear table is divided into b blocks, and the number of elements in every block is s.
因为我们在这个块索引表里面是采用二分检索的方法来查找的，因此， 就跟我们前面二分检索它的平均检索性能个公式相关。 The method we retrieving within block index table is dichotomizing retrieval, so the function of chunked retrieval is related to the formula of dichotomizing retrieval’s average search performance.
我们就直接得到这个值。 We can get the value directly.
然后在块内我们是用顺序检索的方法，就得到这个右边这个值。 它的一个平均检索的性能大概就是这样一个数值。 Next we use sequential retrieval to retrieve within the block, so we’ll get a value right here. Its average search performance would be this value approximately.
这个数值我们不是很好分析它的极值的情况，因此我们来简化一下。 Based on this value, we cannot evaluate its extreme accurately, then we should simplify it,
假设在这个索引表里面，也还用顺序检索。 We assume that retrieve the index table by sequential retrieval, too.
在这个块索引表里面平均检索长度就是二分之b+1，而在这个每一块里面，它的平均检索的长度是二分之s+1。 Therefore the average search length of the block index table is b/2+1, while the average search length of every block is s/2+1.
我们得到的这样一个平均检索长度就是这么一个值，因为我们的b乘以s是等于n的， 所以我们这里可以保留这个参数s，然后把这个b我们化解掉，然后得到这个一个跟n和s相关的这么一个函数。 We get the value of the average search length, when we multiply b by s is n, so we can cross out b, keep the parameter, s, and get a function of n and s.
可以看出就是当s等于根号n的时候这个平均检索长度ASL是取到最小值的。 它的值就是根号n加1。 Then we can work out that the average search length (ASL) would get the minimum value when s equals the square root of n.
我们来看一下具体的这么一组数据。 Now we use a series specific data to apply this conclusion.
如果我们待检的数值是一万个的时候，顺序检索是二分之n+1，就是大约是五千次。 而二分检索它是十四次， 分块检索是一百次。 If there are 10,000 data waiting to be retrieved, the average search length of sequential retrieval is n/2+1, it would be about 5,000; while dichotomizing retrieval’s is 14, and chunked retrieval’s is 100.
可以看出这个分块检索是介于顺序检索和二分检索之间， 而它又有更好的维护的一些性能，也就是插入删除的性能。 We can conclude that the performance of chunked retrieval is between sequential retrieval and dichotomizing retrieval, while it could maintain some performances better, namely inserting and deleting.
所以在很多情况下，分块检索是不错的一些方法。 So the chunked retrieval is a pretty way in many cases.
我们来看一下这个分块检索它的优缺点， 首先它的插入删除都是非常方便的，它只是需要在一个块的局部进行调整。 Let's analysis the advantages and disadvantages of chunked retrieval, first of all, it is very convenient to insert and delete, it just needs to be adjusted partially within the block.
插入它是找到相应块之后，就在这个块的尾部直接插入。 而删除只需要移动这个块里面的相应的一些比较少数的记录，没有大量记录的移动。 We can insert an element directly after the end of this block when the corresponding block is found. And this only needs to move a small number of the corresponding records inside of the block instead of moving a large number of them when we delete any element.
而它的缺点就是，首先我们要额外地建立一个辅助的这样一个索引的空间， 而且我们最开始的时候对整个线性表就要进行这个分块排序， 就是块跟块之间要保持一个序。 The disadvantage is that we need to build such an auxiliary index space externally, and when we start on the table, we should carry out chunked sequence of entire linear table, to maintain a sequence among these blocks.
另外如果是插入、删除特别频繁的情况下，有些块可能被删空了，而有些块可能就是插入插满了， 因为我们这个分块的检索我们还是把这个元素放在一个顺序表里面，你这个满了以后你必然就挤到它的邻居块里面去。 Moreover, if we insert or delete very frequently, some blocks may become empty by deleting, while some may become full by inserting. Because we have chunked retrieval, we’d better put the element in a sequential table. When the table is full, the element will be pushed into the next block.
这样的话我们就要对整个线性表要进行重新的组织。 If that happens we will have to re-organize the whole linear table.
最后，我们留几个思考。 Finally, I question a few problems for you to think.
首先是比较一下顺序检索、二块检索和分块检索它们各自的优缺点。 The first is to compare the advantages and disadvantages of sequential retrieval, dichotomizing retrieval and chunked retrieval.
另外讨论一下，这几种检索方法它所适合的应用场景各是什么样的。 Then discuss what application scenarios are suitable for these types of retrieval method.
谢谢大家。 Thank you!