衬衫争夺战 版权说明：《Bad Choices》是由Ali Almossawi著作的一套计算思维书籍，可以通过https://bookofbadchoices.com/访问本书英文版本。书中通过一系列人物的故事场景，以插画的方式展示了一个个现实生活中遇到的问题，进而引出了一些计算思维的问题，内容丰富且非常有趣。本书的目标读者是计划学习编程的儿童、学生，通过阅读本书可以开拓眼界，培养计算思维习惯。
本章背景故事（请孩子阅读，家长伴听）
你是否遇到过这种场景呢——某个商场计划5.1搞超级大促销活动，结果在当天早上9：00商场开门之前，门口就挤满了人。整点开门后，大家蜂拥进去抢购自己需要的商品。
这一章我们的主人公ET是一名护士，她就面临这类似的状况，由于商场打折促销力度很大，她 提前一天晚上就在商场外面扎了帐篷露营，准备开门后进去抢购自己心仪的衬衫。她的衬衫尺码很常见是M号，她想确保自己是第一个进店的人，这样她就可以拿到所有符合她尺码的衬衫。
让我们先想象一下 ET会如何冲进商店：她的脸可能被涂上了迷彩颜色，格子披肩在背后翻滚，战斗呐喊从她嘎嘎作响的牙齿上迸出，她紧贴商店入口的大门，而其他人则紧随其后。
前提：衣架非常长；衣架上的衣服已经按照从左到右的顺序尺码依次增加，也就是
XXXS，XXS，XS，S，M，L，XL，XXL，XXXL
目标：对于给定的衣架，找到适合她尺寸的衬衫。
方法 一：对于给定的衣架，从一端到另一端查看衬衫。
方法 二：对于给定的衣架，开始在靠近中间的地方寻找正确的衬衫尺码。如果中间的衬衫比她的尺码大，向左移动；如果比她的尺码小，向右移动。
好了，现在我们可以动手准备了，请你找到笔和纸、袜子（可选）或者其他你觉得可以替代的道具。
你可以按照上面的两种方法，先进行一些实验，看看哪种方法会更快？并思考为什么？
实验完成再接着往下看哦！
衬衫争夺战 分析过程（请家长+孩子分段阅读思考）
我们面临着要在一堆东西中寻找一件商品的问题。
第一种方法是线性寻找的方式。通常情况下，假设这堆东西有100件，我们一般会可能会需要把每一件都看一遍而后找到，而这种寻找时间是线性的，也就是说，我们在100件里面找一件需要1分钟，如果变成200件了，我们所需要的时间会变成2分钟，这样消耗的时间会比较长。
第二种方法则是利用了这个衣服架已经做了排序的特点，通过从中间起步查找，实现在对数时间内找到匹配的衬衫。对数是指数的逆运算，就像2的3次方是8，那么log2 8，也就是8件衣服需要分三次拆分出来，而log2 100约等于6.64，也就是7次左右。在这种方法使用上，我们利用了两个因素，一是我们的前提条件，就是衣服按照尺码进行了排序，二是ET的尺码是M，通常会落在在中间部分。
当线性时间转化为对数时间，我们可以看到这种改进是多么巨大。对于100件衬衫的情况下，搜索不到七步，在一个假设一千件衬衫的架子中也只有十步左右。这种在排序集合中对数搜索的方法称为二分搜索法。
相对于线性法，对数法最有价值的一点是，随着衬衫数量的增多，所消耗的时间增长不是很大，这种特点使我们在处理更大数据的时候，使用对数法尤其高效。
今天学习结束了，下面一起来通过实验体会一下学到的方法吧！
衬衫争夺战 本章延申练习（请家长+孩子共同完成）
对数法可以应用的场景很多，比如你在查找字典的时候，翻电话号码本查号等等，你们也可以做一个数字猜谜游戏：爸爸心里想一个100以内的数字，由孩子报出数字，并给出提示“大了”“小了”，看看什么方法更快的猜到这个数字？体会这一过程。
Written By