什么是二分查找

二分查找，也称为折半查找，是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两部分，每次比较中间元素与目标值，如果目标值等于中间元素，则找到；如果目标值小于中间元素，则在左半部分继续查找；如果大于中间元素，则在右半部分查找。这个过程会一直持续到找到目标值、数组为空或者越界为止。由于每次都是对一半的数据进行比较，所以时间复杂度为O(log n)，效率较高。

我们用图示的方法来简单表示一下二分查找和解释一下二分查找的时间复杂度：

最好的情况复杂度很容易计算，那么我们来探讨最坏的情况复杂度是怎么计算出来的：
我们以中间值一直大于目标值为例，每次进行查找之后，中间值左边部分元素的个数就会变成原来的1/2。

以此内推，当我们查找到最后一个元素的时候，我们可以得到N/2/2/2/2…/2=1。我们设查找了X次，则2^x=N，那么最坏的情况下时间复杂度为O(x)，也就是

因为这样的复杂度不好写，所以我们一般简化为O(logN)，这个写法的前提条件是底数为2。

二分查找这个算法的厉害之处在哪里呢？假如我们我们已知一个有序数组，它的元素个数为N，那么我们一个一个的遍历的去寻找目标值，它的时间复杂度为O(N),当N为1000时，我们要查找1000次，N为10亿，就要查找10亿次，这个是很麻烦的；而用二分查找这个算法的时候，N为1000它只需要查找10次，N为10亿它只需要查找30次。时间效率非常的快。但二分查找在实际情况下并不实用，因为它有个前提条件，就是这个数组必须是有序的。