Array algorithms
C Programming Lesson 10 2:30 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Four jobs come up again and again with arrays, and they look like four different recipes.
在数组上反复出现的有四件事，它们看起来像四种不同的做法。
They are not.
其实不是。
Every one of them is the same loop over every item, with one variable that remembers something different.
每一件都是同一个遍历所有元素的循环， 只是那个用来“记住”的变量不同。
Remember the biggest so far and you have a maximum.
记住目前为止最大的，就得到最大值。
Remember how many passed a test and you have a count.
记住有多少个通过了检查，就得到计数。
Remember where it was found and you have a search.
记住它是在哪里被找到的，就得到查找。
Remember the running total and you have a sum, and then an average.
记住累计的总和，就得到求和，进而得到平均值。
Learn the skeleton once and all four are yours.
把这个骨架学会一次，四件事就都是你的了。
The maximum has one trap, and it is in the very first line.
求最大值只有一个陷阱，而且就在第一行。
It is tempting to start it at zero and then keep anything bigger.
人很容易把它初始化为 0，然后保留任何更大的数。
Try that on an array where every number is negative and it answers zero — a value that is not even in the array.
在一个所有数都是负数的数组上试试，它会回答 0—— 而这个值根本不在数组里。
Start from the first item instead.
应该从第一个元素开始。
That is guaranteed to be a real member, so whatever wins from there is real too.
它一定是数组里真实存在的成员， 所以从那里胜出的那个，也一定是真实的。
A search is the one that leaves early.
查找是那个会提前离开的算法。
Check each item, and the moment it matches, return straight away — and return the index, the place, not the value, because the caller already knows what it asked for.
逐个检查，一旦匹配，就立刻返回—— 而且返回的是下标，也就是位置，不是值， 因为调用者本来就知道自己找的是什么。
If the loop runs all the way out, nothing matched, so return minus one.
如果循环一直跑到结束，说明没有任何元素匹配，那就返回 -1。
That is the standard signal, and it works because minus one is never a valid index.
这是通用的约定，之所以可行，是因为 -1 永远不会是合法的下标。
Zero cannot do this job: zero is a real position.
0 做不了这件事：0 是一个真实的位置。
Now the lesson's fourth task, the average — and lesson two's trap is waiting in it.
现在做课程里的第四道题，求平均值——第二课的陷阱正埋在里面。
Add every item into an int total, which is fine.
把每个元素加进一个 int 的 total，这没问题。
Then divide by n, and you are dividing two ints again, so C throws the fraction away and seven point five arrives as seven.
然后除以 n，这时你又是在拿两个 int 相除， 于是 C 把小数部分丢掉，7.5 变成了 7。
Declaring the function's return type as double does not save you; the division has already happened by then.
把函数的返回类型写成 double 救不了你；到那时除法早就做完了。
Cast one side to double first, and the answer keeps its decimals.
先把其中一边转成 double，答案才会保留小数。
Four things to take with you.
带走四点。
One: all four jobs are one scan with a different memory.
第一：这四件事都是同一次遍历，只是记住的东西不同。
Two: for a maximum, start from a real item, never from zero.
第二：求最大值时，要从数组里真实存在的元素开始，绝不要从 0 开始。
Three: a search hands back the index, or minus one for not found.
第三：查找返回的是下标，找不到就返回 -1。
Four: cast before dividing, or your average is an int.
第四：先做类型转换再相除，否则你的平均值就是个整数。
Now write all four; each one is about five lines.
现在把四个都写出来；每一个大约五行。