很多同学初学Scratch编程的时候，一般都编写过一个叫《猜数字》的游戏，游戏的内容是让计算机随机生成一个1-100范围内的数字，给你十次机会，看你能否猜中。我估计很多同学都猜中了，你还记得自己用的是什么方法吗？是的，你一定会“往中间猜”。举例来说，你第一次一定会猜50，这是1-100之间的数字，如果计算机说小了，你就会在51和100之间再找中间数，如果计算机说大了，你会在1-49之间再找中间数……直到猜中为止。在你为自己的成功兴奋不已的时候，有没有想到，你无意中掌握了一项强大的数据查找技术——二分查找算法呢？
本节我们来做一个二分查找的应用。
问题
用户指定一个整数范围，并假想此范围内的任意一个数字，由计算机猜测此数字，猜中时给出使用的次数。
分析
原来是计算机设置数字我们来猜，现在反过来了，我们设置一个数字让计算机来猜——计算机没有程序是什么都做不了的，因此我们就得编程告诉它怎么“猜”，这就要把上面我们自己用到的“二分查找”算法实现出来，交给计算机去执行。
二分查找又称折半查找、二分搜索、折半搜索等，它适合于在有序的的序列中查找目标元素。比如我们刚刚说的一个范围内的整数，这肯定是一个有序序列。我们可以把从中查找一个数字的过程描述如下（假设这个）： – 1、假设要查找的范围是从A到B的序列，A、B都是整数，且B大于A。 – 2、找到A、B范围内的中间元素M，和要查找的元素比较，相等表示查找成功，如果中间元素M大于目标元素，表明目标元素在M左边，这时把查找范围设置为A至M-1之间的数字；反之如果中间元素M小于目标元素，表明目标元素位于M右边，这时把查找范围设置为M+1到B之间的数字。 – 3、重复第二步直到找到目标元素，因为我们设置的是A、B之间的整数，不会存在找不到的情况。
我们来举个例子。假如我们要让计算机猜的是1-10之间的一个数字7，则 – 计算机首先在1-10之间取中间值，中间值 M=1+向下取整((10-1)/2) = 5
- 你会告诉计算机，小了，于是计算机进行第二次查找，把范围缩小到了6和10之间，最小值变成了M+1=6，而中间值 M=6+向下取整((10-6)/2) = 8
- 你会告诉计算机，大了，于是计算机进行第三次查找，把范围缩小到了6和7之间，原来的最大值变成了M+1=7，中间值 M=6+向下取整((7-6)/2) = 6
- 现在，你会告诉计算机，还是小了点。计算机毫不气馁进行了第四次查找：中间值 M=7+向下取整((7-7)/2) = 7
- 找到了！这个时候如果你想逗一逗计算机，说还是小了，计算机经过验证发现不对，再算一遍还是这个数字呀，就不毫不客气地回你一句：你要找的就是这个数！
编程
其实有了上面的分析，程序就相当简单了。我们一起来看看：
一、设置四个角色，一个是计算机，就是负责猜我们设置的数字的角色，其余是三个按钮，分别显示“大了”、“小了”、“正确”用于我们给计算机反馈。设置最大数、最小数、中间数、次数、最大次数、计算乘方六个变量。编写程序让用户输入最大数、最小数，对这个范围进行判断，如果设置不合理（最大数<最小数）就停止程序（拒绝继续猜了），然后计算最大次数（这是通过将变量“计算乘方”不断乘2直到大于序列中的数字个数，这个时候乘2的次数就是计算机猜出我们设置的数字最多要用的次数），接着进行第一次猜数字，等待你的反馈：
二、下面是“猜大了”按钮的代码，其余两个和它类似，只是回馈的消息不同，分别是“猜对了”和“猜小了”。
三、计算机根据反馈进行再次运算：
四、程序完成！
总结
你可能意识不到二分查找的威力。由于每次会缩小一半的查找范围，这种效率是很惊人的，将来你如果学了对数运算，就知道我们的查找次数是怎么算出来的了。现在，如果你试着在程序运行时指定一个范围1-100,000，即1到10万，计算机马上告诉你，我最多用17次就可以找到这个数字，你相信吗？不信就试试。
