给孩子的第一本编程思维启蒙书

4.5 速寻宝石

在一堆宝石中如何找出瑕疵的那一颗,当宝石不多的时候我们可以一个个的比对, 当宝石非常多的时候,使用折半查找算法能很快帮助我们找出瑕疵宝石。

思路解析

天秤称重

把宝石平分成两份,拿到天平中去称重,重的那一边包含瑕疵宝石。

循环重复

将重的一边再次平分,如此一来每称重一次都可以排除一半,如果数目是奇数没法继续平分的话就从好的宝石中拿一颗过来。

高效解决

按照这样的方法,1W颗宝石的话我们也只需要10几次就能找出瑕疵的宝石,编写好程序计算机很快就能找到答案。