看完这篇文章你就彻底懂啦｛保姆级讲解｝-----（LeetCode刷题704、35、34数组二分查找） 2023.4.17

前言

本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可，撰写本文章主要目的在于记录自己学习体会并分享给大家，全篇并不仅仅是复制粘贴，更多的是加入了自己的思考，希望读完此篇文章能真正帮助到您！！！

数组的定义

数组是由n（n>=1）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围为数组的维界。
由上图可知：

1. 数组下标都是从0开始的
2. 数组内存空间的地址是连续的

数组的存储结构

对于多维数组，有两种映射方式，按行优先和按列优先。以二维数组为例，按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。

算法题（LeetCode 704.二分查找）—（保姆级别讲解）

力扣题目链接

分析题目

1. 处理数据类型为整型数组
2. 该数组为有序数组即升序数组
3. 该数组中的元素是不重复的
4. 上述条件中的2和3是我们决定使用二分查找的关键

什么是二分查找？

我们会使用有序索引数组来表示被查找的目标值target可能存在的子数组的大小范围。在查找时，我们先将被查找的目标值和子数组的中间值比较。如果被查找的目标值小于中间值，我们就在左子数组中继续查找，如果大于，我们就在右子数组中继续查找，否则中间值就是我们要找的目标。

算法思想（重要）

二分查找其实有两种写法：

1. 左闭右闭-----------[left, right]
2. 左闭右开-----------[left, right)

*至于为什么是两种写法后面会阐述，但是在这里我想声明一点，第二种写法本人不推荐，徒增算法难度，我们学习算法的初心不是算法越难越好，而是如何用最简单的算法思想解决我们的问题，这才是最主要的。所以本篇文章不会讨论第二种，如果对第二种写法感兴趣的可以自行探索。 *

第一种写法代码：

// (写法一) 左闭右闭区间 [left, right]
int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize-1;
    int middle = 0;
    
    while(left<=right) {
        middle = (left+right)/2;  
        if(nums[middle] > target) {
            right = middle-1;
        } 
        else if(nums[middle] < target) {
            left = middle+1;
        } 
        else if(nums[middle] == target){
            return middle;
        }
    } 
    return -1;
}

时间复杂度：O（log n）

空间复杂度：O（1）

好！按照老样子，接下来开始详细讲解每行代码的用处，以及为什么这样写！

int search(int* nums, int numsSize, int target)

//函数入口参数分别为int* nums, int numsSize, int target，其中nums是int类型的指针，指向了其目标数组，numsSize为数组元素个数，target为数组目标值。

 int left = 0;
 int right = numsSize-1;
 int middle = 0;

//初始化部分，左边界left初始化为0（因为数组下标是从0开始的），右边界right初始化为numsSize-1（因为数组下标是从0开始的，也就是0~numsSize-1），middle初始化为0（也就是计算中间值的下标）

 while(left<=right) 

//熟悉二分查找的都应该知道最终只会有三种情况，分别是left>right,left=right,left>right，当left>right证明该算法已经遍历结束也就代表其目标数组中没有我们要寻找的目标值（target）。

 middle = (left+right)/2;  

//计算中间值下标的公式，举个例子，假设目标数组中有6个元素，即下标为0~5，那么在第一次二分查找时计算middle值为（0+5）/2 = 2，即下标为2对应的middle值与target值比较大小。

if(nums[middle] > target) {
	right = middle-1;
	} 

//根据二分查找的算法思想可知，当中间值大于target值时，意味着target值可能位于[left,middle-1]这个区间内，所以需要将right赋值为middle-1。

else if(nums[middle] < target) {
	left = middle+1;
	} 

//根据二分查找的算法思想可知，当中间值小于target值时，意味着target值可能位于[middle+1,right]这个区间内，所以需要将left赋值为middle+1。

else if(nums[middle] == target){
	return middle;
	}

//根据二分查找的算法思想可知，当中间值等于target值时，意味着当前遍历的middle下标对应的值即为我们所寻找的目标值。

 return -1;

//如果都不满足上述条件，则代表目标数组中没有我们所寻找的目标值。

为了更能让大家了解二分查找的算法思想，作者特意画了一张图供大家观看！！！

第二种写法代码（本人不推荐）：

// (版本二) 左闭右开区间 [left, right)
int search(int* nums, int numsSize, int target){
    int length = numsSize;
    int left = 0;
    int right = length;	//定义target在左闭右开的区间里，即：[left, right)
    int middle = 0;
    while(left < right){  // left == right时，区间[left, right)属于空集，所以用 < 避免该情况
        int middle = left + (right - left) / 2;
        if(nums[middle] < target){
            //target位于(middle , right) 中为保证集合区间的左闭右开性，可等价为[middle + 1,right)
            left = middle + 1;
        }else if(nums[middle] > target){
            //target位于[left, middle)中
            right = middle ;
        }else{	// nums[middle] == target ，找到目标值target
            return middle;
        }
    }
    //未找到目标值，返回-1
    return -1;
}

时间复杂度：O（log n）

空间复杂度：O（1）

//第二种写法相对于第一种写法的主要区别在于右边界right下标的选取，举个例子，初始阶段，left = 0，但是第二种写法中将right下标设置为numsSize，而不是第一种写法的numsSize-1，虽然改动了这个，但是在以后的判断中间值和target值时，会增加一些难度，例如当中间值大于target值时，意味着target值可能位于[left,middle-1]的区间内，但是由于是第二种写法，所以这里就只需将middle值赋值给right值即可，细心一点会发现和middle值小于target值的情况处理是不一样的，所以在实际的编写算法过程中容易犯错，徒增算法难度。所以第二种写法本人不推荐（没必要和自己过不去，懂得都懂）。

算法题（LeetCode 35.二分查找）—（保姆级别讲解）

力扣链接

分析题目

1. 处理数据类型为整型数组
2. 该数组为有序数组即升序数组
3. 该数组中的元素是不重复的
4. 上述条件中的2和3是我们决定使用二分查找的关键

算法思想（重要）

//版本一 [left, right]左闭右闭区间，版本二 [left, right]左闭右开区间不推荐（不推荐理由见本文章中有介绍）
int searchInsert(int* nums, int numsSize, int target){
    //左闭右开区间 [0 , numsSize-1]
        int left =0;
        int mid =0;
        int right = numsSize - 1;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(target < nums[mid]){
                right = mid -1;
            }else if( target > nums[mid]){
                left = mid + 1;
            }else {
                return mid;
            }
        }
        //数组中未找到target元素
        //target在数组所有元素之后，[left, right]是右闭区间，需要返回 right +1
        return right + 1;
}

可以发现35题和704题代码大致相同，唯一一点是最后的找不到目标值，即在本题目中找不到其所需要插入的位置时，需要返回right + 1，接下来我们来细细讲一下找不到目标值的情况。
找不到目标值大致分为三种情况：

1. 目标值在数组所有元素之前
2. 目标值插入数组中的位置
3. 目标值在数组所有元素之后

为了更能让大家了解找不到目标值的三种情况，作者特意画了一张图供大家观看！！！

算法题（LeetCode 34.二分查找）—（保姆级别讲解）

力扣链接

分析题目

1. 处理数据类型为整型数组
2. 该数组为非递减顺序数组

算法思想（重要）

其实本题题目中已经很清楚表示最终需要找到目标值在数组中的开始位置和结束位置即该问题又可转化为寻找左边界和寻找右边界。所以接下来我们分别探讨这两个问题。
寻找左、右边界又需要考虑三种情况，如下所示：

1. 寻找左边界

int getLeftBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; 
    int leftBorder = -2; 
    while (left <= right) {
        int middle = left + ((right - left) / 2);
        if (nums[middle] >= target) { 
            right = middle - 1;
            leftBorder = right;
        } else {
            left = middle + 1;
        }
    }
    return leftBorder;
}

2. 寻找右边界

int getRightBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; 
    int rightBorder = -2; 
    while (left <= right) { 
        int middle = left + ((right - left) / 2);
        if (nums[middle] > target) {
            right = middle - 1; 
        } else { 
            left = middle + 1;
            rightBorder = left;
        }
    }
    return rightBorder;
}

分析 :

跟前面两个算法我们对比下，其实细心一点会发现最大的改变有两处，分别是：

1. 增加了leftBorder和rightBorder这两个变量，代表边界
2. 增加了leftBorder = right;和 rightBorder = left;这两个语句。

为了更能让大家了解这两个不同之处，作者特意画了一张图供大家观看！！！

反思：

从前很喜欢一句话，在这里分享给大家：

告诉我，我会忘记！
给我看，我可能记住！
让我参与其中，我才会理解！

所以我就在想如果经过一段时间后，让我重新再做这道题，我还能不能完整写出来？
那么问题来了，其实和前两个算法我的思考在于两个方面，分别是（以寻找左边界为例）：

1. leftBorder = right;（为什么寻找左边界，是right赋值给leftBoder）
2. if (nums[middle] >= target) {
   right = middle - 1;
   leftBorder = right;}（为什么leftBorder = right;这个语句在这个if语句里，而不是在else语句里）

针对上面两个思考，我给出自己的理解

1. 寻找左边界的代码最终返回的变量是leftBoder，在该算法执行的过程中可以发现，因为寻找的是左边界问题，所以相当于是right值不断从右往左减少，即leftBoder是随着right值的趋势改变的。（寻找右边界同理）

2. 

主体代码：

左右边界计算完之后，看一下主体代码，这里把上面讨论的三种情况，都覆盖了

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 情况二
        return {-1, -1};
    }
private:
     int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
};

其中针对这行代码做一些解释：

// 情况三
if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};

因为本算法的功能是计算出来的右边界是不包含target的右边界，左边界同理。

结束语

如果觉得这篇文章还不错的话，记得点赞 ，支持下！！！