【优选算法】—— 二分查找

序言：

• 本期，我们将要介绍的是有关 二分查找算法 并通过题目帮组大家更好的理解！

（一）基本介绍

1、基本思想

二分查找算法（Binary Search Algorithm）是一种在有序数组中查找目标值的高效算法。它的基本思想是将数组分成两部分，然后通过比较目标值和数组的中间元素，确定目标值可能存在的位置，然后将搜索范围缩小一半，逐步逼近目标值的位置，直到找到目标值或确定目标值不存在。

2、解题流程

以下是二分查找算法的详细过程：

1. 初始化左指针（left）为数组的起始位置，右指针（right）为数组的末尾位置。
2. 计算中间位置的索引（mid），mid =  left + (right - left) /2
3. 将目标值与中间位置的元素进行比较：

• 若目标值等于中间位置的元素，找到目标值，返回中间位置的索引。
• 若目标值小于中间位置的元素，说明目标值可能在数组的左半部分，将右指针（right）更新为 mid - 1，继续执行步骤 2。
• 若目标值大于中间位置的元素，说明目标值可能在数组的右半部分，将左指针（left）更新为 mid + 1，继续执行步骤 2。

4. 重复执行步骤 2 和步骤 3，直到找到目标值或确定目标值不存在。即当左指针大于右指针时，表示搜索范围为空，目标值不存在。

3、复杂度以及注意事项

二分查找算法的时间复杂度为 O（log n），其中 n 是数组的大小。由于每次都将搜索范围缩小一半，因此算法的效率非常高。

二分查找算法的前提是数组必须是有序的，如果数组无序，则需要先进行排序操作。此外，二分查找算法还可用于在旋转有序数组中查找目标值，只需要在比较大小时增加一些额外的判断条件。

需要注意的是，二分查找算法适用于静态数组或只读的情况。如果需要频繁地插入或删除元素，会导致数组的重新排序，影响二分查找的优势。

【小结】

• 总结起来，二分查找算法是一种高效的查找算法，适用于有序数组中查找目标值。它的核心思想是通过不断缩小搜索范围，以有效地定位目标值。

（二）题目讲解

接下来，我们通过具体的题目带着大家去进行理解相关算法。

1、在排序数组中查找元素的第⼀个和最后⼀个位置

【算法思路】

1. ⽤的还是⼆分思想，就是根据数据的性质，在某种判断条件下将区间⼀分为⼆，然后舍去其中⼀个区间，然后再另⼀个区间内查找；
2. ⽅便叙述，⽤ x 表⽰该元素， resLeft 表⽰左边界， resRight 表⽰右边界。

【寻找左边界思路】

寻找左边界：

◦ 我们注意到以左边界划分的两个区间的特点：

1. 左边区间 [left, resLeft - 1] 都是⼩于 x 的；
2. 右边区间（包括左边界） [resLeft, right] 都是⼤于等于 x 的；

• 因此，关于 mid 的落点，我们可以分为下⾯两种情况：

1. 当我们的 mid 落在 [left, resLeft - 1] 区间的时候，也就是 arr[mid] <target 。说明 [left, mid] 都是可以舍去的，此时更新 left 到 mid + 1 的位置，继续在 [mid + 1, right] 上寻找左边界；
2. 当 mid 落在 [resLeft， right] 的区间的时候，也就是 arr[mid] >= target 。说明 [mid + 1, right] （因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界；

• 由此，就可以通过⼆分，来快速寻找左边界；

注意：这⾥找中间元素需要向下取整

因为后续移动左右指针的时候：

• 左指针： left = mid + 1 ，是会向后移动的，因此区间是会缩⼩的；
• 右指针： right = mid ，可能会原地踏步（⽐如：如果向上取整的话，如果剩下 1,2 两个元素， left == 1 ， right == 2 ， mid == 2 。更新区间之后， left，right，mid 的值没有改变，就会陷⼊死循环）

因此⼀定要注意，当 right = mid 的时候，要向下取整。

【寻找右边界思路】

寻右左边界：

◦ ⽤ resRight 表⽰右边界；

◦ 我们注意到右边界的特点：

1. 左边区间（包括右边界） [left, resRight] 都是⼩于等于 x 的；
2. 右边区间 [resRight+ 1, right] 都是⼤于 x 的；

• 因此，关于 mid 的落点，我们可以分为下⾯两种情况：

1. 当我们的 mid 落在 [left, resRight] 区间的时候，说明 [left, mid - 1]（ mid 不可以舍去，因为有可能是最终结果）都是可以舍去的，此时更新 left 到 mid 的位置；
2. 当 mid 落在 [resRight+ 1, right] 的区间的时候，说明 [mid, right] 内的元素是可以舍去的，此时更新 right 到 mid - 1 的位置；

• 由此，就可以通过⼆分，来快速寻找右边界；

注意：这⾥找中间元素需要向上取整

因为后续移动左右指针的时候：

• 左指针： left = mid ，可能会原地踏步（⽐如：如果向下取整的话，如果剩下 1,2 两个元素， left == 1， right == 2，mid == 1 。更新区间之后， left，right，mid 的值没有改变，就会陷⼊死循环）。
• 右指针： right = mid - 1 ，是会向前移动的，因此区间是会缩⼩的；

因此⼀定要注意，当 right = mid 的时候，要向下取整。

【代码展示】

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 处理边界情况
        if(nums.size() == 0) 
            return {-1, -1};  
        //创建一个变量来记录结果的左端点
        int begin = 0;
        // 1. ⼆分左端点
        int left = 0;
        int right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }    
        // 判断是否有结果
        if(nums[left] != target) 
            return {-1, -1};
        else 
            begin = left; // 标记⼀下左端点   
        // 2. ⼆分右端点
        left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return {begin, right};
    }
};

【解释说明】

1. 在边界情况下，如果给定的数组为空，则直接返回结果为{-1, -1}。
   
2. 创建一个变量来记录结果的左端点。begin
   
3. 初始化左右指针和分别指向数组的起始位置和末尾位置。left right
   
4. 第一个while循环是为了找到目标值的左端点，使用二分查找的思想。

• 将中间位置的索引计算为，这是一个向下取整的操作。mid = (left + right) / 2
• 如果中间位置的元素小于目标值，说明目标值可能在右半部分，将左指针更新
• 否则，目标值可能在左半部分或者当前位置为目标值的左端点，将右指针更新为。right = mid
• 重复上述操作，直到和指针相等时退出循环。left = right

5. 判断是否等于目标值，如果不等于，则说明目标值不存在于数组中，返回结果为{-1, -1}。nums[left] = target
   
6. 否则，标记左端点位置为。begin = left
   
7. 第二个while循环是为了找到目标值的右端点，同样使用二分查找的思想。

• 将中间位置的索引计算为，这个是为了取整到右边的元素。mid =(left + right + 1) / 2
• 如果中间位置的元素小于等于目标值，说明目标值可能在右半部分或者当前位置为目标值的右端点，将左指针更新
• 否则，目标值可能在左半部分，将右指针更新为。right = mid - 1
• 重复上述操作，直到和指针相等时退出循环。left = right

8. 返回结果为{, }，即目标值的范围。
   

【性能分析】

1. 这段代码可以在时间复杂度为O（log n）的时间内找到有序数组中目标值的范围，其中n是数组的大小；
2. 两次二分查找分别找到目标值的左右端点，从而确定目标值在数组中的范围。

2、搜索旋转排序数组中的最⼩值

【算法思路】

题⽬中的数组规则如下图所⽰：

其中 C 点就是我们要求的点。

⼆分的本质：找到⼀个判断标准，使得查找区间能够⼀分为⼆。

通过图像我们可以发现， [A，B] 区间内的点都是严格⼤于 D 点的值的， C 点的值是严格⼩

于 D 点的值的。但是当 [C，D] 区间只有⼀个元素的时候， C 点的值是可能等于 D 点的值。

因此，初始化左右两个指针 left ， right ：

然后根据 mid 的落点，我们可以这样划分下⼀次查询的区间：

1. 当 mid 在 [A，B] 区间的时候，也就是 mid 位置的值严格⼤于 D 点的值，下⼀次查询区间在 [mid + 1，right] 上；
2. 当 mid 在 [C，D] 区间的时候，也就是 mid 位置的值严格⼩于等于 D 点的值，下次查询区间在 [left，mid] 上。

当区间⻓度变成 1 的时候，就是我们要找的结果

【代码展示】

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        int x = nums[right]; // 标记⼀下最后⼀个位置的值
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > x) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};

【解释说明】

1. 初始化左右指针和分别指向数组的起始位置和末尾位置。leftright
   
2. 创建一个变量来存储数组最后一个位置上的值，即数组中的最大值。这是为了标记最后一个位置的值，以便在最后返回最小值。xnums[right]
   
3. 进入while循环，判断条件是，即左指针小于右指针时执行循环。left < right
   
4. 将中间位置的索引计算为，这是一个向下取整的操作。mid(left + right) / 2
   
5. 比较中间位置的元素和最后一个位置的值。nums[mid]x

• 如果，说明最小值在mid的右侧，将左指针更新
• 否则，最小值可能在mid的左侧或者就是当前位置mid，将右指针更新为。
• 重复上述操作，直到和指针相等时退出循环。

6. 循环结束后，返回，即找到的最小值。nums[left]
   

【性能分析】

1. 时间复杂度为O（log n）的时间内找到旋转排序数组的最小值，其中n是数组的大小；
2. 通过二分查找的方式逐渐缩小查找范围，最终找到最小值的位置。

3、搜索二维矩阵

【算法思路】

1、初始化两个指针，一个指针指向二维矩阵的左上角，即第一行第一列的元素，另一个指针指向二维矩阵的右下角，即最后一行最后一列的元素。利用这两个指针来缩小搜索范围。

2、在每次循环中，首先比较左上角指针所指的元素与目标值的关系：

• 如果左上角指针所指的元素等于目标值，说明找到目标值，返回true。
• 如果左上角指针所指的元素大于目标值，说明目标值可能在左上角指针所在的列的左侧，将右下角指针的列数减1。
• 如果左上角指针所指的元素小于目标值，说明目标值可能在左上角指针所在的行的下方，将左上角指针的行数加1。

3、重复步骤5，直到左上角指针的行数大于右下角指针的行数或者左上角指针的列数大于右下角指针的列数，表示搜索范围已经缩小到无法再继续缩小的情况

【代码实现】

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) 
        {
            return false;
        }
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0;
        int right = m * n - 1;
        
        while (left <= right) 
        {
            int mid = left + (right - left) / 2;
            int row = mid / n;
            int col = mid % n;
            
            if (matrix[row][col] == target) 
            {
                return true;
            } 
            else if (matrix[row][col] < target) 
            {
                left = mid + 1;
            } 
            else 
            {
                right = mid - 1;
            }
        }
        
        return false;
    }
};

【解释说明】

1. 首先检查矩阵是否为空，如果是空矩阵，则直接返回。
   
2. 获取矩阵的行数和列数。
   
3. 初始化左指针为0，右指针为矩阵总元素数减1。
   
4. 进入while循环，判断条件是，即左指针小于等于右指针时执行循环。left <= right
   
5. 计算中间位置的索引，使用进行计算。mid=(left + right) / 2
   
6. 根据中间索引计算出对应的行和列，通过和分别得到行和列的值。
   
7. 将矩阵中对应的元素与目标值进行比较。

• 如果等于，则找到目标值，返回。
• 如果小于，说明目标值可能在当前位置的右侧，将左指针更新。
• 如果大于，说明目标值可能在当前位置的左侧，将右指针更新。
• 重复上述操作，直到找到目标值或者左指针大于右指针时退出循环。

8. 循环结束后，如果没有找到目标值，返回。
   

【性能分析】

• 该算法的时间复杂度为O（m+n），其中m为二维矩阵的行数，n为二维矩阵的列数。算法利用了二维矩阵的特点，在每次比较后可以减少一行或一列的搜索范围，从而快速找到目标值或确定不存在目标值。

总结

请⼤家⼀定不要觉得背下模板就能解决所有⼆分问题。⼆分问题最重要的就是要分析题意，然后确定要搜索的区间，根据分析问题来写出⼆分查找算法的代码。

• 要分析题意，确定搜索区间，不要死记模板，不要看左闭右开什么乱七⼋糟的题解
• 要分析题意，确定搜索区间，不要死记模板，不要看左闭右开什么乱七⼋糟的题解
• 要分析题意，确定搜索区间，不要死记模板，不要看左闭右开什么乱七⼋糟的题解

重要的事情说三遍。

【模板记忆技巧】

• 1. 关于什么时候⽤三段式，还是⼆段式中的某⼀个，⼀定不要强⾏去⽤，⽽是通过具体的问题分析情况，根据查找区间的变化确定指针的转移过程，从⽽选择⼀个模板。
• 2. 当选择两段式的模板时： 在求 mid 的时候，只有 right - 1 的情况下，才会向上取整（也就是 +1 取中间数）

以上便是关于 二分查找 算法的全部知识讲解！大家多加练习，立即这部分算法还是很轻松的！