OK? So the example I'm going to do, I'm going to search a sorted list.
来搜索目标元素,好,翻到课堂材料的第二页。
Again. Basic premise of binary search, or at least we set it up was, imagine I have a sorted list of elements. We get, in a second, to how we're going to get them sorted, and I want to know, is a particular element in that list..
好,二分查找的基本前提,或者是我们建立二分查找的基础,我们已经有了一个排好序的元素列表,我们就需要知道如何来快速的排序,如何从列表中找到特定的元素。
We don't seem to be doing that just yet, certainly not as badly, alright, so at this point in the story I have a sorted list of size 4.
当然现在我们不需要那样做,此时此刻,我已对整个问题中大小为4的列表排好序了。
If we could do sort, then we saw, if we amortized the cost, that searching is a lot more efficient if we're searching a sorted list.
如果我们可以做排序,然后我们可以看到,如果我们分摊开支,在有序列表中搜索将会变得更高效。
Well let's see. My fall back is, I could just do linear search, walk down the list one at a time, just comparing those things. OK. So that's sort of my base. But what if I wanted, you know, how do I want to get to that sorted list? All right?
我只能做线性搜索了,一次遍历一遍列表,一个一个比较,但如果我想要,那怎样得到有序的列表呢?,现在的一个问题是,我们排序之前?
Where in the worlddid that sorted list come from?
如果我只是有一系列的元素,那怎么办呢?
You'll also notice that this thing goes through the entire list, even if the list is sorted before it gets partway through.
你也能注意到,它始终会遍历列表,甚至列表在排序之前,就是有序的也是这样。
This list is sorted and that is, you know, stupid to say but it's very much correct.
这个序列是有序的,虽然有点愚蠢,但却是正确的。
This is sorted, this is sorted, how do I now make a list of size 2?
这个是有序的,这个也是有序的,我怎样才能组成一个有2个元素的列表?
This list is sorted, this list is sorted but they could be intermingled.
这个序列是有序的,这个也是有序的,可以将它们组合起来。
Alright, so the list is now hopefully sorted correctly and it is, in fact.
现在,整个列表已经正确地,排好序了。
So now, I have a list that's sorted of size 2.
现在大小为2的列表已排好序了。
And this is now consistent with my claim that I have sorted a list of size N equals 1.
这与我之前所说的是一致的,我已经将N为1的一个序列排好了序。
I remind you, I know you're not really listening to me, but that's OK. I reminded you at the beginning of the lecture, I said, let's assume we have a sorted list, and then let's go search it.
没关系,我告诉过你在课程的开始,我们假设这是一个排好序的列表,然后才进行的搜索,那实际上有序列表从哪里来的呢?
If I look for, say, minus 1, you might go, gee, wait a minute, if I was just doing linear search, I would've known right away that minus one wasn't in this list, because it's sorted and it's smaller than the first elements.
如果我要查找-1,你可能要怒了,呵呵,等一等,如果我用的是线性查找,我不会知道-1不在这个列表中,但是列表是排好序的,1又比第一个元素小。
And the example I want to look at is, suppose I want to search a list that I know is sorted, to see if an element's in the list.
看看目标元素在不在数组里,也就是说我要去,检索一个有序的数组。
This list is sorted.
这个序列也是有序的。
So to just preface what we're going to do next time, what would happen if I wanted to do sort, and rather than in sorting the entire list at once, I broke it into pieces, and sorted the pieces, and then just figured out a very efficient way to bring those two pieces and merge them back together again?
所以为了引导下一次,我们要讲的内容,如果我想做排序,而且不是一次吧整个列表排完,会发生什么,我把它拆成小的列表,然后把各个小列表排序,接着用高效的方法再把小的列表?
Basic idea, before I even look at the code, is pretty simple. If I've got a list that is sorted, in let's call it, just in increasing order, and I haven't said what's in the list, could be numbers, could be other things, for now, we're going to just assume they're integers.
我们可以说基本的思想是很简单的,如果我有一个排好序的数组,让我们认为这个数组是递增的吧,我并没说数组里元素是什么,可能是数字,也可能是其他的东西,现在我们假设是integer类型的数字吧,最简单的方式就是这么做了:
应用推荐