二分查找

转眼十年过去，还记得2009年学习数据结构的时候，那时候觉得最好理解的就是二分查找这个概念。时光转眼即逝，这么些年过去，好多底层基础知识不使用，基本都忘记的差不多了。

不过二分查找这个概念倒还是能够想起来，因为这个概念是当年学习这门课觉得最容易理解的知识点。二分查找就是每次比较要查找的数和中间数据的大小，直到找到数据为止。

现在再来总结一下

二分查找的时间复杂度为O(logn)，空间复杂度为O(1)

二分查找使用场景

1, 二分查找依赖的数据结构是顺序的线性表，就是数组。能够方便的访问数组的下标元素，不适合于链表，链表的访问时间复杂度为O(n)。

2，数组本身必须是有序的。最好是静态的数据资源，不适合动态的数据源。

3，必须有一定的数据量，不然顺序查找和二分查找速度没有多少差异。

4，不能有非常的数据量，不然没有足够连续的内存空间来保存数据。

二分查找算法代码

二分查找算法注意点

1，循环条件是low<=high,而不是low<high,不然会导致value=high时无法查找到。

2，mid计算使用移位效率高于/2。

3，缩小区域查找时low=mid+1或者high=mid-1;而不是low=mid或者high=mid,这样会导致死循环low一直等于high。

二分查找使用场景变体

一般对于在某个顺序表中查找某个值相等的场景多半会使用二叉查找树。二分查找多使用在寻找近似值的场景中，如下四种场景：

1，查找有序数组中首次等于某固定值的序号。

2，查找有序数组中最后一次等于某固定值的序号。

3，查找有序数组中首次大于某固定值的序号。

4，查找某有序数组中最后小于等于某固定值的序号。

场景3的代码如下：