AI_第一部分 数据结构与算法（14.二分查找算法）

第四阶段我们进行深度学习(AI)，本部分（第一部分）主要是对底层的数据结构与算法部分进行详尽的讲解，通过本部分的学习主要达到以下两方面的效果：

1.对开发中常见的算法能应用自如，让你在跳槽找工作中“算法题”不再是阻碍你“钱途”的拦路虎。

2.我们不需要调参数的调参攻城狮，我们要做正真的自己的AI模型。

3.本部分预计40篇左右。

hello,大家好，今天我们聊一个简单点的话题，二分查找，当年那个找你妹游戏大家还记得吗，哈哈，要想快速的找到，那你也是需要有策略的，今天我们就聊聊二分查找算法。

我们先看一张图：

二分查找是有前提的：就是数据是按照一定顺序递增或者递减。在此前提下，每次都与区间的中间数据比对大小，缩小查找区间的范围。其中，low 和 high 表示待查找区间的下标，mid 表示待查找区间的中间元素下标。

总结一下：二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二分查找的时间复杂度是O(logn),为何如此之快呢？

假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。可以看出来，这是一个等比数列。其中 n/2k=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。

在写代码之前，我们先看看那些点是容易搞错的：

1. 循环退出条件

注意是 low<=high，而不是 low<high。

2.mid 的取值

实际上，mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是将 mid 的计算方式写成 low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以2操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。

3.low 和 high 的更新

low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。比

如，当 high=3，low=3 时，如果 a[3] 不等于 value，就会导致一直循环不退出。

好的，说完注意的点，我们来看一下python 实现的代码：

def bsearch(nums, target):
    """Binary search of a target in a sorted array
    without duplicates. If such a target does not exist,
    return -1, othewise, return its index.
    """
    low, high = 0, len(nums) - 1  # 获取最小、最大下标
    while low <= high:  # 最小下标不超过最大下标时:
        mid = low + (high - low) // 2  # 二分点
        if nums[mid] == target:  # 二分点的值与目标值相等
            return mid  # 返回其下标
        elif nums[mid] < target:  # 小于
            low = mid + 1  # 最小值下标移动到二分点下一个位置
        else:  # 大于
            high = mid - 1  # 最大值下标移动到二分点前一个位置
    return -1

好的，本期我们对于二分查找算法就算彻底说完了，如果有问题可以进行留言,本期的完整代码请访问我的github自行获取。地址为：https://github.com/haishiniu/Data-Structure-and-Algorithms/tree/master/b_s，如果可以，请大家fork 一下这个代码库，谢谢啦。