共计 946 个字符，预计需要花费 3 分钟才能阅读完成。
二分查找是一种非常简单易懂的疾速查找算法，生存中到处可见。比如说，咱们当初来做一个猜字游戏。我随机写一个 0 到 99 之间的数字，而后你来猜我写的是什么。猜的过程中，你每猜一次，我就会通知你猜的大了还是小了，直到猜中为止。你来想想，如何疾速猜中我写的数字呢？
无处不在的二分思维
二分查找是一种非常简单易懂的疾速查找算法，生存中到处可见。比如说，咱们当初来做一个猜字游戏。我随机写一个 0 到 99 之间的数字，而后你来猜我写的是什么。猜的过程中，你每猜一次，我就会通知你猜的大了还是小了，直到猜中为止。你来想想，如何疾速猜中我写的数字呢？
假如我写的数字是 23，你能够依照上面的步骤来试一试。（如果猜想范畴的数字有偶数个，两头数有两个，就抉择较小的那个。）
7 次就猜出来了，是不是很快？这个例子用的就是二分思维，依照这个思维，即使我让你猜的是 0 到 999 的数字，最多也只有 10 次就能猜中。不信的话，你能够试一试。
看懂这两个例子，你当初对二分的思维应该把握得妥妥的了。我这里略微总结升华一下，二分查找针对的是一个有序的数据汇合，查找思维有点相似分治思维。每次都通过跟区间的两头元素对比，将待查找的区间放大为之前的一半，直到找到要查找的元素，或者区间被放大为 0。
二分查找惊人的查找速度
二分查找是一种十分高效的查找算法，高效到什么水平呢？咱们来剖析一下它的工夫复杂度。咱们假如数据大小是 n，每次查找后数据都会放大为原来的一半，也就是会除以 2。最坏状况下，直到查找区间被放大为空，才进行。
能够看进去，这是一个等比数列。其中 n /2k= 1 时，k 的值就是总共放大的次数。而每一次放大操作只波及两个数据的大小比拟，所以，通过了 k 次区间放大操作，工夫复杂度就是 O(k)。通过 n /2k=1，咱们能够求得 k =log2n，所以工夫复杂度就是 O(logn)。
残缺内容请点击下方链接查看：
“二分”带来“非常”快感——二分思维的神秘解析
版权申明：本文内容由阿里云实名注册用户自发奉献，版权归原作者所有，阿里云开发者社区不领有其著作权，亦不承当相应法律责任。具体规定请查看《阿里云开发者社区用户服务协定》和《阿里云开发者社区知识产权爱护指引》。如果您发现本社区中有涉嫌剽窃的内容，填写侵权投诉表单进行举报，一经查实，本社区将立即删除涉嫌侵权内容。
