初识算法 · 二分查找(1)

前言：

本文呢，我们从滑动窗口窗口算法移步到了二分查找算法，我们简单了解一下二分查找算法，二分查找算法是一个十分恶心，十分注重细节，但是同时也是十分简单的一个算法，有人好奇，注重细节和简单怎么能挂的上关系呢？这是因为二分查找对于边界的处理是尤其要小心的，所以对于二分查找来说，将边界处理好了，自然就简单多了，相当于套了一个模板。那么本文呢，通过两个题目，简单介绍一下二分查找算法。

704. 二分查找 - 力扣（LeetCode）

35. 搜索插入位置 - 力扣（LeetCode）

本文的讲解呢，通过三部曲，是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。

二分查找

题目解析

题目的名称是二分查找，非常朴素的一个标题，根据题目要求，需要我们找到target所在位置。并且返回对应对应的下标，如果没有就返回-1。

那么根据题目，我们能得到的有效信息还有一个是升序。这个条件对于二分查找来说，是十分重要的，之后的二分查找算法，我们本质上不是非要找一个有序的数组才能使用，而是我们需要找到某种特定的规律，可以将整个数据区间划分为两端，简称为二段性，而因为二分查找实际上也是双指针，但是因为特别突出，所以单独拿出来，通过某种特定的规律。实现某种需求，这是二分。

暴力解法都不用说，直接就是一个循环搞定，但是自然时间复杂度是O(N)，如果是其他题目，O(N)已经是很快了，但是如果有42亿个数字呢？查找42亿次不免太慢了。

所以我们进入到算法原理部分。

算法原理

通过题目解析，我们知道了如果直接遍历，是O(N)，相对来说比较高，那么我们从暴力解法中优化。

比如我们查找的区间是1，2，3，4，5，6，7，8，9。查找的target是5，我们选取任意一点，比如7，因为数组是有序的，所以7后面的数都比5大，我们就不用去7的后面找了。这就是优化，即选取特定的点，从该点开始改变左右指针的位置，一次性干到一大片的数据。

那么此时点的选择就尤为重要了，如果是选择三分之一的位置，运气好点，可能就会将三分之二的数据干掉，在数学中，有一个词叫做数学期望，我们肯定是期望能一次干掉最多的数据，最保险的肯定就是从中间开始选择点。

那么边界处理部分，也就是判断之后如果大于left指针怎么移动或者是right指针怎么移动，这是要考虑的。

所以最朴素的二分查找，无非就是确定左右中指针，判断，改变指针位置，每次干掉一半的数据，就这么多，没有了，那么还有两种模板，我们放在后面介绍。

算法编写

class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1, mid = -1;
        while(left <= right)
        {
            mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) right = mid - 1;
            else if(nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
};

首先判断结束条件是left是否超过了right，如果超过肯定是不可以的，因为是二分查找，所以最坏的情况也就是查找到最后一个数据，也就是区间只有一个数据，此时left是等于right的。

那么关于mid，使用left + (right - left + 1) / 2主要是为了防止溢出，如果直接(right + left) / 2，可能来整型相加会有溢出的风险，所以left + (right - left) / 2是为了放溢出，至于+1和不加一这道题是没有区别的。

这是最经典的二分查找算法，时间复杂度显然为O(logN)，为什么二分查找快呢？如果查找42亿个数，暴力需要找42亿次，二分查找只需要找32次，十分的快。

搜索插入位置

题目解析

这个题目可以说是上一个题目的翻版，不过是多加了一个要求，如果没有找到对应的元素，我们就应该返回按顺序插入的下标。

那么这里，其实是使用了除了朴素模板的另外模板的，至于是什么，我们防在第二篇二分查找里面介绍。题目信息还有一个升序，也就没有什么了，这个题目一看就是二分查找，所以暴力解法咱也就不说了。

直接进入算法原理部分。

算法原理

我们做二分查找算法的题目的时候，第一个肯定是要找什么可以导致二段性，这道题是升序吗？还是target和其他位置的大小关系呢？

实际上，对于是否能不能找到该数据是不重要的，我们应该关心的是，如何插入的问题？

我们可以将数据区间分为[left,index] [index + 1,right]，而left所在的区间是比target小的，我们根据示例分析，就可以最后插入是只要找到刚好比target大的那个数就可以，也就是左区间的最后一个数。

所以如果Mid小于target，left = mid + 1就可以了，那么如果mid > target，right = mid，因为mid如果落在了右区间，是有可能找到最后我们的答案的。

这个基本模板套出来，题目也就做出来了，但是我们要防止的是如果插入的位置是数组之外，就应该另外判断一下。

算法编写

class Solution 
{
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1, mid = 0;
        while(left < right)
        {
            mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[right] < target) return right + 1;
        return right;
    }
};

感谢阅读！