14天算法入门第一天：二分查找算法，长文详解，包教包会！

一、算法详细讲解 1.0 前言介绍

讲解已经非常详细，尽量是让小白都能学会，因此如果你觉得自己算法并不是很好，或者没有基础，那我希望你一定要认真看我写的每一句话，同时要学会自己思考，不然对你也收获不大。

1.1二分查找介绍

二分查找也叫做折半查找。查找也是有特殊情况的，比如数列本身是有序的。这个有序数列是怎么产生的呢？有时它可能本身就是有序的，也有可能是我们通过之前所学的排序算法得到的。

1.2二分查找条件

由上面的讲解可以知道，二分查找有两个要：，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）

二、 原理及实现

二分查找的实现原理非常简单，首先要有一个有序的列表。但是如果没有，则该怎么办？可以使用排序算法进行排序。 以升序数列为例，比较一个元素与数列中的中间位置的元素的大小，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数列长度都会是之前数列的一半，直到找到相等元素的位置或者最终没有找到要找的元素。

三、时间复杂度

我们先来想象一下，如果数列中有 3 个数，则先与第 2 个数进行比较，如果比第 2 个数大，则与第 2 个数右边的数列进行二分查找，这时这个数列就剩下一个数了，直接比较是否相等即可。所以在 3 个数的时候最多比较两次。

同理，在有 4 个数的时候，我们与中间数进行比较，一般中间数是首加末除以 2 算出来的，这时我们算出来的中间数是 (1+4)/2 等于 2，所以我们把要查找的数与第 2 个数比较，若比第 2 个数小，则直接与第 1 个数比较；否则与后面两个数进行二分查找，这时的中间数是 (3+4)/2 等于 3，也就是后半部分的第 1 个数。再接着进行比较，相等则找到相应的元素，小于则没有这个数（因为左边所有的数都已经判断过了），大于则继续向右查找。所以在 4 个数的时候最多比较 3 次。 以此类推，在 5 个数的时候最多查找 3 次，在 6 个数的时候也是最多查找 3 次。 时间复杂度：O(logN)

四、算法

画个图便于理解，我把一整个数组划分为三个部分，头部，尾部，中部。 我们每一次查找要么在后半区查找，要么在前半区查找。比如我要在前半区查找，那后半区我们就不要了，high就要移动到mid前一个，mid就要移动到low与mid之间。也就是形成一个新的减半数组。

4.1非递归思想

算法如下，具体再看注释：

//非递归思想
int search(SeqList r, int k)
{//在r[1....n]中查找k
    low = 1; high = n;
    while (low  r[mid].key)  low = mid + 1;//在后半区查找
        else high = mid - 1;//继续在前半区查找

    }
    return 0;//查找失败返回0
}

4.2递归思想

算法如下，具体再看注释：

//递归思想
in search1(SwqList r, int k, in low, int high)
{
    if (low > high) return 0;//排除不合法数组
    mid = (low + high) / 2;
    if (k == r[mid].key)  return mid;//找到待查找元素
    else if (k > r[mid].key)
        return search1(r, k, mid + 1, high);//low变成了原来的mid前，继续查找后半区
    else
        return search1(r, k, low, mid - 1);//继续查找前半区
}

五、Leecode案例 5.1例一

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

我们套上面讲的算法模板，代码为：

int search(int* r, int n, int k)
{//在r[1....n]中查找k
   int low = 0;int high = n-1;
    while (low  r[mid])  low = mid + 1;//在后半区查找
        else high = mid - 1;//继续在前半区查找

    }
    return -1;//查找失败返回0
}

执行结果：

5.2案例二

套算法模板！！！ 题目：你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。 代码：

int firstBadVersion(int n) {
    int left = 1, right = n;
    while (left  1) + left;
        if (target