学点不一样｜二分查找是什么？

vlambda
2020-11-05

学点不一样｜二分查找是什么？

点击蓝字

故事背景

今天是暑假第⼀天

初中⽣都放假了，⼩明和⼩花打算玩个猜数字游戏。⼩明要⼩花⼼中想⼀个范围是[1,1000]的数字，⼩明来猜这个数字。如果⼩明猜的这个数字⽐⼩花想的要⼤，⼩花就说⼤了；如果⼩明猜的这个数字⽐⼩花想的要⼩，⼩花就说⼩了，⼀直到⼩明猜中为⽌。

第⼀轮游戏开始：⼩花⼼⾥想的数字是 8，⼩明说：1，⼩花说⼩了；⼩明说 2，⼩花说小了；⼩明说：8，⼩花说：你真厉害，才⽤了 8 次就猜对了。⼩花想再玩⼀次，⼩明特别爽快的就答应了。

第⼆轮游戏开始：⼩花⼼⾥⾯想的数字是 900，⼩明说：1，⼩花说⼩了；⼩明说 2，⼩花说⼩了；⼩明说：800，⼩花说：⼜⼩了。这个时候天已经⿊了，⼩明的妈妈叫他回去吃饭，⼩明⾮常沮丧，⼩花安慰⼩明说：不要伤⼼，明天我们再来玩猜数字的游戏，教你⼀个⽅法，保证你每次猜的时候都能很快猜到这个数。⼩明⾼兴地蹦回了家。

第二天

⼩明和⼩花再次玩起了猜数字的游戏，⼩花要⼩明在⼼⾥⾯想⼀个数字，⼩明想了 173。

⼩明⾮常惊讶：⼩花居然只要 9 次就能猜出我⼼⾥⾯想的数字，⽽且这个数字还这么⼤，好厉害！⼩花你⽤了什么神奇的读⼼术？

⼩花说：我刚才猜数字所使⽤的是"⼆分查找"的思想。简单来说就是，每⼀次猜测，我都选取了当前这段整数范围的中位数，这是效率最⾼的策略。

⼩明说：为什么这样效率最⾼呢？

⼩花说：因为我每次选择的数字，你⽆论说偏⼤还是偏⼩，我都可以让剩下的选择范围缩⼩⼀半。接下来我就⽤图⽚演示⼀下我⼼⾥⾯的选择过程，看好了，读⼼术开始！

给定范围 0 到 1000 的整数：

第⼀次我选择 500，发现偏⼤了，

那么我下⼀次的选择范围，就变成了 1 到 499：

第⼆次我们选择 250，发现还是偏⼤了，

那么下⼀次的选择范围，就变成了 1 到 249：

第三次我们选择 125，发现偏⼩了，

那么下⼀次的选择范围，就变成了 126 到 249：

以此类推，最坏的情况需要猜测多少次呢？

答案是 log1000 = 10次，也就是说⼩明你不管⼼⾥想的数字是多少，我最多只要猜测 10 次就可以读出你⼼⾥⾯想的数字。这就是我⾼效读⼼术的秘诀，现在就分享给你了。以后千万不要顺序查找了，⽤⼆分查找可以让你查找效率翻倍。

⼩明：⼩花，真的太感谢你了，妈妈再也不⽤担⼼我不能准时回家吃饭了！⼩明⾼⾼兴兴回到家之后，打开家⻔⼝邮箱，看到⽼师寄过来的期末考试成绩单和班级排名表，但是⼩明的成绩单上⾯只有成绩 332 分，没有班级排名，⼩明特别期待知道⾃⼰这次期末考试在全班的排名，因为有进步的话，妈妈承诺了要给⼩明奖励，打开班级成绩表之后，从第⼀名开始找⾃⼰的名字，找了前⼗名都没发现⾃⼰的名字，⼩明眼睛有点累了，突然⼩明想到了今天⼩花教给他的⼆分查找法。

下⾯是这次期末考试⼩明班级的排名表，你能在 6 次⽐较之内找到⼩明（张仕明）的排名吗？

END

撰稿：肖世飞

图文编辑：刘路琼

vlambda博客
学习文章列表