一图学懂信奥赛基石级考点：二分查找
本篇文章 818 字，3 张图片，预计 7 分钟读完，收下这份二分查找的入门攻略，快来学习吧~
关于二分查找如何学习，网络上有很多的资料，难点在于孩子如何能把这种抽象的算法具象化。
今天，小蒜头换一种方式为大家讲解 CSP-J/S 初赛、复赛中基石级地位的知识点：二分查找。
想象生活中遇到这样一个问题：有 16 个不同的数字按照升序排列，现在我想要知道数字 x 在数列中的哪一个位置？
正常思路：一般情况下，我们会从第一个数字开始去寻找，直到找到数字 x，我们就知道它的位置了。
二分查找：神奇的二分查找算法就可以更高效的找到它的位置！
Step1：首先我们要明确查找区间：最左边是 1，最右边是 16，接下来我们在这个区间中得到区间的中间位置 mid，也就是 8 这个位置。如果这个位置的数就是 x 的话，我们一次就得到了答案，如果小于 x 的话，说明区间 [1，mid] 的所有数均小于 x，直接就可以舍弃掉这部分数了，所以令新的查找区间为 [mid+1,16]。同理，如果大于 x 的话，说明区间 [mid, 16] 的所有数均大于 x，可以直接舍弃，新的查找区间为[1 , mid]。
Step2：我们可以在新的查找区间里面进行多次同样的操作，不断的缩小查找区间，直到找到数字 x 为止。
估计很多同学看到这里已经炸了，没关系，前面的可以不用再看了
，直接理解下面这个图：
1）右下角是二分查找的算法；
2）右上角是每一行代码的解读；
3）左半部分是每一行代码的执行效果，与代码一一对应。
△二分查找演示
当然，二分查找只是信息学学习中众多抽象概念中的其中一个知识点，类似这样的抽象概念如递归、栈等还有很多。
赞 (0)