『算法』『数据结构』 浅谈二分算法，理解程序员必懂必会的计算机常见算法

二分算法，又名二分查找、折半查找，是一种查找算法，是最基础的，最简单易学且高效实用的算法之一。二分算法的时间复杂度为：O(logN)。因此基本上做题中大部分要求时间复杂度与’logN’有关的，都要考虑会用到二分算法。

二分查找操作的数据集是一个有序的数据集。开始时，先找出有序集合中间的那个元素。如果此元素比要查找的元素大，就接着在较小的一个半区进行查找；反之，如果此元素比要找的元素小，就在较大的一个半区进行查找。在每个更小的数据集中重复这个查找过程，直到找到要查找的元素或者数据集不能再分割。

可用二分算法解决的问题必须满足以下两个条件： 1.序列必须是有序的且连续的； 2.答案可以在一定范围内判断（在序列中）。

而且因为二分算法的时间复杂度为：O(logN)，基本上只要看到题目中要求的时间复杂度与’logN’有关的，且满足以上两个条件的，都要用到二分算法来解决。

有时，使用二分查找满足条件的两个数时，通常把一个数遍历，时间复杂度O（N）；另一个数二分查找判断是否满足条件，复杂度O（logN）。所以总的时间复杂度是O（N*log（N））

二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。在以下介绍的实现方法中，有序数据集存放在sorted中，sorted是一块连续的存储空间。参数target是要查找的数据。 此实现过程的实施是通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。首先，将left和right分别设置为0和size-1。在循环的每次迭代过程中，将middle设置为left和right之间区域的中间值。如果处于middle的元素比目标值小，将左索引值移动到middle后的一个元素的位置上。即下一组要搜索的区域是当前数据集的上半区。如果处于middle的元素比目标元素大，将右索引值移动到middle前一个元素的位置上。即下一组要搜索的区域是当前数据集的下半区。随着搜索的不断进行，left从左向右移，right从右向左移。一旦在middle处找到目标，查找将停止；如果没有找到目标，left和right将重合。

注意：二分算法一定要注意周全的考虑边界值的情况和许多细节，二分算法很容易在细节上犯错。

猜数游戏问题： 假设我们来玩一个猜数的游戏，假设有一个人要我们猜0-99之间的一个数，猜错了我会告诉你是大了还是小了，如何最快的猜出这个人要我们猜的数字？

解题思路： 最好的方法就是从0-99的