之前我们对两种searching algorithms——linear search（线性检索）和binary search(二分检索)以及两种sorting algorithms——selection sort和insertion sort进行了非常详尽的学习，梳理了它们的逻辑，并分析了它们的基本代码，还有图示辅助理解。（apcsa考试题型：searching algorithms和sorting algorithms分析）

今天呢，我们将一起梳理AP CSA中关于searching & sorting的一些常见的考法，并总结解题思路。 

1. Questions of Searching

关于searching的选择题主要有下面几种常见的考法： 

A. Value Returned

题目有可能给出searching method的代码和具体的参数值，然后询问这个method的返回值。

让我们一起来看看下面这两道例题： 例1:What would the following code return from mystery ([90, -30, 50], 50)?

A. -1

B. 0

C. 1

D. 2

E. 50

【答案解析】

题目所给的代码很明显是linear search的代码：一一检索序列中的每一个元素，如果程序在序列int[] elements中找到了和int target值相同的元素，返回这个元素所在位置j。 题目使用方法mystery，并输入参数（[90, -30, 50], 50），告诉程序我们想要检索的序列int[] elements是[90, -30, 50]，想要寻找的target值是50。因为50在序列[90, -30, 50]里，所以代码会返回50所在的位置index：2，应该选择D。  怎么样，做对了吗？

我们再来看下第二道例题： 例2:What would the following code return from binarySearch ([90, -30, 50], 60)?

A. -1

B. 0

C. 1

D. 2

E. 60

【答案解析】

题目所给的代码明显是binary search的代码：所以先找到序列最中间的元素，和目标值比较，如果相等则返回中间元素的index，否则缩小寻找返回。 虽然binary search的代码看起来要比linear search复杂一些，但它们执行的功能是一样的：找到目标值，返回元素所在位置；没找到，就返回-1。题目使用方法binarySearch，并输入参数（[90, -30, 50], 60），告诉程序我们想要检索的序列int[] elements是[90, -30, 50]，想要寻找的target值是60。因为60不在序列[90, -30, 50]里，代码就只好返回-1啦。  

这边老师给大家总结一下解题思路：

【易错点】

别忘了array里元素的index是从0开始的！例如，在array[90, -30, 50]里，90的index是0（而不是1），-30的index是1，50的index是2。 都会了吗？那来做个小练习检验下吧~

练习1：What would the following code return form mystery ([90, -30, 50], -20)?

A. -1B. 0C. 1D. 2E. -20

【答案解析】

还记得前面的三步答题步骤嘛？ 

Step1：首先，我们可以识别出题目给的是linear search的代码

Step2：然后，我们知道目标序列int[] elements是[90, -30, 50]和目标值int target是-20

Step3：最后，因为目标值-20不在目标序列里，所以代码会返回-1，因此答案选择A  

B. Number of Loops Needed

另外一种常见的题型是：给出searching method的代码和具体的参数值后，询问method需要运行多少遍loop (for loop 或者 while loop)后:

1）才能找到特定目标元素；

2）或者才能确定特定目标元素不在序列中。 

比如这道题目： 例3:Consider the binarySearch method below. How many times would the while loop execute if you first do int[] arr = {2, 10, 23, 31, 55, 86} and then call binarySearch(arr, 2)?

A. 1B. 2C. 3

这道题询问我们，代码要运行多少次while loop才能在序列中arr找到-2。 让我们简单分析一下过程：1st pass: left = 0, right = 6-1 = 5, middle = (int) [(0 + 5) / 2] = 2, 中间值为arr[2] = 23;

目标元素2小于中间值23，所以我们不再考虑23以右的比它更大的元素们，缩小搜索范围, right = 2 – 1 = 1。 2nd pass:  left = 0, right = 1, middle = (int) [(0 + 1) / 2] = 0, 中间值为arr[0] = 2;

目标元素2等于中间值2，我们找到了目标元素，代码返回目标元素所在的位置middle = 0，停止运行while loop。 所以代码需要运行2次就可以在序列中arr找到-2，答案选择B。 

【解题思路】

遇到这种问“要进行多少次循环才能找到目标元素”的题目，关键是找到每一次运行while loop后的中间值，直到中间值等于目标元素，再数我们一共列出了几个pass（也就是loop运行了几次）。

题目的另一种问法是“要进行多少次循环才能确定目标元素不在序列里”，比如这道题: 例4:

【思考】

这一小问询问我们，为了检索目标元素27，binary search运行一次for loop后，我们的搜索范围会缩小成什么样子。我们可以直接开始分析： 1st pass：left = 0, right = 7, middle = (int) [(0 + 7) / 2] = 3, 中间值为arr[3] = 11;目标元素27大于中间值11，所以我们不再考虑11以左的比它更小的元素们，缩小搜索范围, left = 3 + 1 = 4。 也就是说，经过1st pass后，我们缩小的检索范围的左临界点left = 4， 右临界点不变right = 7，新检索范围是a[4]到a[7]，选择C。 （接上题） 

第二道题问的是要进行多少次循环才能确定目标元素不在目标序列里。分析方法和例3是非常类似的：

1st pass:left = 0, right = 7, middle = (int) [(0 + 7) / 2] = 3, 中间值为arr[3] = 11;目标元素27大于中间值11，所以我们不再考虑11以左的比它更小的元素们，缩小搜索范围, left = 3 + 1 = 4。

2nd pass: left = 4, right = 7, middle = (int) [(4 + 7) / 2] = 5, 中间值为arr[5] = 24;目标元素27大于中间值24，所以我们不再考虑24以左的比它更小的元素们，缩小搜索范围, left = 5 + 1 = 6。

3rd pass：left = 6, right = 7, middle = (int) [(6 + 7) / 2] = 6, 中间值为arr[6] = 30;

目标元素27小于中间值30，所以我们缩小搜索范围, right = 6 - 1 = 5。

注意了！这时left = 6大于right = 5，已经不满足继续运行while loop的条件left <= right了，所以程序会退出while loop，返回-1。 因此，确定27不在序列里需要运行3次循环。

【解题思路】

遇到问“要多少次循环才能确定找不到目标元素”的题目，分析方式和“找到目标元素”很相似，关键是找到每一次运行while loop后的中间值，直到left>right退出while loop，再数我们一共列出了几个pass（也就是loop进行了几次）。 

【解题技巧】

以下是一种解这种题目的套路，记下来或许可以救急用：

Reference: Barron's Ap Computer Science A (7thEdition)

但老师还是更推荐同学们自己去对具体题目进行分析，像我在上文列出来的分析过程一样，这样比较保险哦~  

C. Comparison Between Sequential Search and Binary Search（比如前提条件、效率等）

关于两种search algorithms的对比，主要得记住两个比较重要的点：

1）使用binary search的前提条件是array里的elements已经被排列好了；

2）在这个前提条件满足的情况下，一般情况(average case)下binary search要比sequential search高效。（不过也有例外，最好还是具体条件具体分析，后面的例6就是一个例子。） 这边还是给大家两道例题康康~ 例5:

【解析】记住binary search的前提条件：元素按序排列！选择C。  例6:

Which of the following described all cases when a linear search uses fewer comparisons to find x than would a binary search?

A. It will never use fewer comparisons.

B. When x is in the middle position of the array

C. When x is very close to the beginning of the array

D. When x is very close to the end of the array

E. When x is not in the array

【思考】

在什么情况下linear search进行比较的次数会更少，从而比binary search更高效呢？ 在元素非常靠近array的开头的时候。 我们把情况设想得极端一点，target element就在第一个位置，那么linear search一开头可以找到它，然后停止运行；而binary search得从最中间的元素开始，然后找到序列前1/2的中间元素，再到序列前1/4的中间元素…直到找到第一个元素，退出程序，会比linear search花更长的时间。 

【解题思路】

在什么情况下哪种searching algorithm更加高效这种问题，可以对照着选项设想一些极端情况，比如假设target element就在第一个或最后一个或最中间，模拟一下不同algorithms的运行过程，你就可以找到答案啦！

D. Maximum Searching Time

这类题目会询问在binarySearch中，运行for loop的最大次数是多少，或者in the worst case程序会运行for loop多少次。 “最大次数”或 “worst case” 意味着我们要检索的序列中不包含目标值：如果目标值在序列中的话，程序一找到目标元素，就会返回目标元素的位置，并退出for loop，结束运行了；只有在找不到目标值的情况下，程序才会一遍遍的运行for loop，直到返回-1。 例7: 

【思考】

在binarySearch中，如果目标序列中间元素elements[middle]不等于目标值target，我们会通过把目标序列砍半来缩小寻找范围（至于砍左边还是右边一半得看elements[middle]和target哪个更大，但不影响for loop的运行次数），然后继续比较剩下一半的中间元素和目标值。 在这道题里，假设在elements[middle]不等于target的情况下，我们每次都砍掉右边一半的序列，那么middle的值将依次是：

在for loop运行9次后，middle已经落在了index 0上，程序会自动退出for loop。选项中最接近9次的估计应该是10次，选择B。 这个序列中的元素数量只有600个，不算太多，我们可以把每一次运行结果列出来，但如果我们要估计的序列包含了成千上万个元素呢？把每一次的运行结果都列出来岂不是要花很长时间！ 其实，我们可以从这个比较小的数列中寻找到一些规律。每一次运行for loop其实就是在对序列进行对半砍，直到砍到第一个元素还没找到目标值，于是退出for loop。对半砍的次数与middle的更新次数相等，而middle值由一次又一次的“/2”更新，直到0。 但middle一共更新了多少次呢？如果从后往前看，其实middle就是从0开始，到1，然后不断的*2变成2，4，8，16，32，64，128…直到最接近元素总数600的512=2的9次方。 

不过这只是个粗略的估计，如果对比上图的计算结果，会发先元素数量越多误差越大，但我们只要粗略估计对数量级就好。所以用2的次方估计的话，middle大概更新了9到11次，也就是for loop大概运行了9-11次，因此10次是一个比较好的估计。 

【解题思路】

如果我们要用binary search在一个有n个元素的array里检索某个值，maximum number of iterations 的估计通式是：。

练习2：

这道题给出的序列很大，有1 million(1,000,000) 元素，把每一次循环都列出来很明显是不现实的，这时我们的估计通式就派上用场啦！=1,000,000。，太小了，远远够不到1, 000, 000；，和1, 000, 000很相近了；次方数再大到100，120，甚至1000，结果将远超1million——所以是一个比较合理的估计。 

2. Questions of Sorting Algorithms

A. Best Case & Worst Case

Best case指的是代码运行用时最少的情况，worst case指的是代码运行用时最多的情况。那么针对两种sorting algorithms，它们各自的best case & worst case是什么样的呢？ 对于selection sort而言，它的best case和worst case比较接近，因为它的运行时间和序列的原始状态没太大关系。无论序列里的元素是原本就被排好序了，还是随机分布在各个位置，该进行的比较的次数不会变，而且每执行完一次for loop都一定会进行一次位置交换（哪怕是自己和自己交换）。所以无论原本序列里的元素是怎么排序的，代码的运行时间都差不多。
  

但是对于insertion sort来说，如果我们的目的是把元素从小到大排列的话，它的best case就是序列里的元素在没sort之前就已经从小到大排列好了。在这种情况下，每一个处在位置j的元素只需和前面的元素进行一次比较，因为j总是比前面的元素大，所以while loop不会运行，然后元素j会和自己交换一次。
 

如果我们的目的依然是把元素从小到大排列的话，insertion sort的worst case就是在运行代码之前，目标序列里的元素是从大到小排列的，和我们想要达到的结果恰好完全相反。

在这种情况下，每一个处在位置j的元素都要不停和前面的元素比较，因为j总是比前面的元素小，while loop总是会运行，然后元素j和前面的元素换位置。比较和交换位置的过程会一直进行，直到元素j被换到（还未被处理的序列部分的）第一个位置。 

这边给大家用一个表格总结一下： 

Selection SortInsertion SortBest Caserandom arrangementelements already in sorted orderWorst Caserandom arrangementelements in reversed order 

B. Run-time Comparison

那么在什么样的情况下，运用哪种sorting algorithms最efficient（也就是运行时间最小）呢？ 以下是一个小总结：

Selection sort 和 insertion sort在序列里的元素比较少的时候较常使用，但如果序列很大的话，它们就不那么高效了。 下图对三种sorting方法的运行时间进行了比较： 

所以如果元素不多，三种sorting方法运行时间没有太大差别；但如果元素数量很多，selection& insertion sort的运行效率就没有其他方法高了。 如果对selection sort和insertion sort进行比较，在序列里的大部分元素都按顺序排列好的时候，insertion sort会更高效。因为selection sort总是要进行固定次数的比较和位置交换，但“很多元素已经按序排列”这一情况接近insertion sort的best case，进行比较和位置交换的次数会降低，运行时间也就相应的减少了。

C. Array After nth Pass

还有的题目会问我们，在运行某种sorting algorithms里的循环n次后，序列里的元素的排序情况变成了什么样。 例8: 

【思考】

这道题希望把元素从大到小排序，我们可以简单分析一下每一次循环，然后把结果列出来：

1st pass：i = 0  89 和后面的每一个元素比较，最大的值max=109，所以89和109交换，得到：

109  42  -3  13  89  70  2

2nd pass: i = 1  42 和后面的每一个元素比较，最大的值max=89，所以42和89交换，得到：

109  89  -3  13  42  70  2

3rd pass：i = 2  -3 和后面的每一个元素比较，最大的值max=70，所以-3和70交换，得到：

109  89  70  13  42  -3  2

这样我们就得到3rd pass以后的结果啦！

【解题思路】

解决这类问题的方法其实挺简单粗暴的，把每一次循环后的array都列出就好了。如果代码掌握的不是特别熟练，最好把代码里的每一步的变量更新、元素交换都写出来，这样比较保险妥当，但是会非常费时。最好还是去熟悉一下sorting algorithms的每一段代码起到了什么样的作用，脑子里就可以模拟array发生了什么变化，事半功倍。 

结   语

今天我们梳理了一些关于searching & sorting algorithms的常见考法和解题思路。但实际考场上出现的题目一定会有不同的变形，所以最重要的还是要理解algorithms本身，多做题、多分析、多总结规律，相信大家一定能完美解决关于searching & sorting的问题的！我们下期再见啦！