1.1.2 游戏的秘密——二分搜索技术

猜数游戏最笨的办法就是从0一直猜到100，一个一个地猜，如果纸上的数字是100，那就猜101次，游戏得多么无聊。其实我们没有必要一个一个地猜，可以像小王一样，每次和中间的元素比较，如果比中间元素小，我们就在中间元素的前面查找，如果比中间元素大，我们就在中间元素的后面查找。二分搜索技术其实在我们的日常生活中随处可见，比如，图书馆安检门响了，图书管理员通常会把你借的书的一半过一下安检，来寻找是哪本书引起的，这就是使用二分搜索技术的典型例子。接下来我们详细讲解一下猜数游戏中的二分搜索技术。如图1.1所示，一共有101个数字，我们现在通过二分搜索技术找到数字66。

图1.1 猜数游戏

（1）我们先猜0～100的中间数字，即50，50比66小，我们需要在51～100中接着查找，如图1.2所示。

图1.2 在51～100中查找数字

（2）51～100的中间数字是（100+51）/2=75.5，向下取整是75，75比66大，我们需要在51～74中接着查找，如图1.3所示。

图1.3 在51～74中查找数字

（3）51～74的中间数字是（51+74）/2=62.5，向下取整是62，62比66小，我们需要在63～74中接着查找，如图1.4所示。

图1.4 在63～74中查找数字

（4）63～74的中间数字是（63+74）/2=68.5，向下取整是68，68比66大，我们需要在63～67中接着查找，如图1.5所示。

（5）63～67的中间数字是65，65比66小，我们需要在66～67中接着查找，如图1.6所示。

（6）66～67的中间数字是（66+67）/2=66.5，向下取整是66，我们找到了目标数字，游戏结束，如图1.7所示。

图1.5 在63～67中查找数字

图1.6 在66～67中查找数字

图1.7 找到目标数字66