【算法笔记】二分查找

最近在做算法复健，鉴于我的blog域名难产，暂时寄居在何dalao这里。

什么是二分查找

二分查找又名折半查找。在一个有序数列中查找某个特定数/对象时，可以根据数的大小关系，每次将查找范围缩小到原来的一半，从而将查找所需的时间从O（n）缩小为O(logn).

举例：我需要在[1,4,5,7,12,15,19,27,33,41,49]这11个数中查找27.

如果正常按顺序检索，需要检索8次，当数据范围扩大到n时，时间复杂度为O(n).

如果采用二分查找，查找顺序如下：

1. 记原数组为数组①，比较数组①中间的数（即15）与27的大小关系
2. 由于15<27，检索数组修改为[19,27,33,41,49]，记为数组②
3. 比较数组②中间的数（即33）与27的大小关系
4. 由于33>27，检索数组修改为[19,27]，记为数组③
5. 比较数组③中间的数（由于除法下取整，这里是19）与27的大小关系
6. 由于19<27，检索数组修改为[27]，发现27==27，记录此时27的索引(7)，查找结束。

由于每次都会将检索范围缩小一半，所以时间复杂度为O(log_2n)。

代码实现

这里代码出了点问题，下次再补（咕咕）

实战题目

二分查找可以用于解决“最大值最小”“最小值最大”这样的问题，其应用非常灵活。未完待续。