代码随想录算法训练营第一天 | （二分查找类型）704.二分查找 35.探索插入位置 34.在排序数组中查找元素的第一个和最后一个位置

704.二分查找

文档讲解：代码随想录
视频讲解：手撕二分
状态：复习

循环不变量

解决二分问题首先要找到 循环不变量 ，常用的有两种：

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

在解题过程中始终要保持区间合法

左闭右闭解法（我喜欢的方法）

首先，我们有初始化l = 0, r = nums.size() - 1，因为l和r均可能是target

	int n = nums.size();int l = 0, r = n - 1;

然后，我们要判断区间，首先根据循环不变量 [left, right] ，可以看出，left = right是合法的，所以循环条件要写成left <= right
接着，我们要写判断，如果nums[mid] > target，那么mid一定不是target，而right可能是target，所以我们得出的结果是r = mid - 1。同理可以分析left。最后没找到即返回-1

	while (l <= r){int mid = l + (r - l >> 1);if (nums[mid] > target) r = mid - 1;else if (nums[mid] < target) l = mid + 1;else return mid;}return -1;

综上我们解决此题

class Solution {
public:int search(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n - 1; // 定义target在左闭右闭的区间里，[left, right]while (l <= r) { // 当left==right，区间[left, right]依然有效，所以用 <=int mid = l + (r - l >> 1); // 防止溢出 等同于(left + right)/2if (nums[mid] > target) r = mid - 1; // target 在左区间，所以[left, middle - 1]else if (nums[mid] < target) l = mid + 1; // target 在右区间，所以[middle + 1, right]else return mid; // 数组中找到目标值，直接返回下标}return -1; // 没找到target}
};

左闭右开解法

方法同左闭右闭 ，我把不同之初说明一下。
首先，初始化部分，根据循环不变量[left, right)，我们可以得出，right一定不是target，所以我们初始化l = 0, r = n
然后，循环条件，left一定不等于right，写成left < right
循环结果，如果nums[mid] > target，由于mid和right都不能是结果，所以r =mid
综上所述，我们可以写出代码：

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

35.探索插入位置

个人解题困惑

对最后的返回的值有点模糊

暴力法

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();for (int i = 0; i < n; i++) {if (nums[i] >= target) return i;}return n;}
};

上述方法的时间复杂度是O(n)，但依然可以通过

二分查找

我们先设定区间为左闭右闭区间，即[left, right]
最终，target所在的区间范围就是[right, left]，这样才能退出循环。所以，我们插入的位置就是left或者right + 1

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n - 1;while (l <= r) {int mid = l + (r - l >> 1);if (nums[mid] > target) r = mid - 1;else if (nums[mid] < target) l = mid + 1;else return mid; // 情况一：如果target下标就是mid，那么就直接返回mid即可}// 情况二：如果target比第一个数还小，最后区间范围是[-1, 0]，left是0，返回left// 情况三：如果target在数组范围之中（可相等也可不相等），target所在范围是[right, left],返回left// 情况三：如果target比任何书都大，即[right, left],返回leftreturn r + 1; // 或者 return l;}
};

左开右开

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int l = -1, r = n;// (left, right)// 找到第一个大于等于target元素的下标while (l + 1 < r) {int mid = l + r >> 1;// 确定循环不变量 ：// nums[l] < target// nums[r] >= targetif (nums[mid] < target) l = mid;else r = mid;}// 循环结束，l + 1 = rreturn r;}
};

34.在排序数组中查找元素的第一个和最后一个位置

模板做法

本道题我看代码随想录没有看懂二分查找的思路，故套用之间背的模板解决此题

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size();if (n == 0) return {-1, -1};int l = 0, r = n - 1;while (l < r) {int mid = l + r >> 1;if (nums[mid] >= target) r = mid;else l = mid + 1;}if (nums[l] != target) return {-1, -1};else {int start = l;l = 0, r = n - 1;while (l < r) {int mid = l + r + 1 >> 1;if (nums[mid] <= target) l = mid;else r = mid - 1;}int end = l;return {start, end};}}
};

这个模板运用的也是左闭右闭，只不过它的循环条件是l < r，这个最终是收缩到一个点，而mid = l + r >> 1是向下取等，当r = mid时采取这个；mid = l + r + 1 >> 1是向上取等，当l = mid时采取这个。
start 和 end 返回 l 或 r 都是可以的。

左开右开做法 (left, right)

首先我们要初始化，l = -1, r = n
确定循环不变量，找左边界时 nums[left] < target，nums[right] >= target；找右边界时nums[left] <= target，nums[right] > target。
最后我们找到l 和 r 的最终位置关系，即 l + 1 = r

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size();int l = -1, r = n, start, end; // 初始化// 选择全开区间(l, r)// l 和 r之间一定有数，所以循环条件是 l + 1 < rwhile (l + 1 < r) {// 确定循环不变量:// nums[l]<target : l及l的左侧均小于target// nums[r] >= target : r及r的右侧均大于等于targetint mid = l + r >> 1;if (nums[mid] < target) l = mid;else r = mid;}// 循环结束后 left + 1 = right// 此时 nums[left] < target, nums[right] >= target// 所以 right 就是第一个 >= target 的元素下标start = r; // 注意：start一定要在循环外赋值// 如果nums[]为空那么start == n// 如果 target 不在nums[]中if (start == n || nums[start] != target) return {-1, -1};l = -1, r = n; // 重新赋值while (l + 1 < r) {// 循环不变量：// nums[l] <= target// nums[r] > targetint mid = l + r >> 1;if (nums[mid] > target) r = mid;else l = mid;}end = l;return {start, end};}
};

易错：1）初始化l = -1， r = n2）循环不变量找错，要通过循环不变量来确定最终边界是 l 还是 r3）start 和 end 要在循环体外进行赋值

左闭右开做法

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n, start, end;// 选择左闭右开[left, right)while (l < r) {int mid = l + r >> 1;// 确定循环不变量：// nums[left - 1] < target// nums[right] >= targetif (nums[mid] < target) l = mid + 1;else r = mid;}// 循环结束，left = right// 此时， nums[l -1] < target  nums[l] = nums[right] >= target// 所以 left就是第一个>=target的元素下标start = l;if (start == n || nums[start] != target) return {-1, -1};l = 0, r = n;while (l < r) {int mid = l + r >> 1;// 循环不变量：// nums[left - 1] <= target// nums[right] > targetif (nums[mid] <= target) l = mid + 1;else r = mid;}// 循环结束left = right// nums[left - 1] <= target  nums[right] > target// 那么left - 1就是第一个 <= target 的元素下标end = l - 1;return {start, end};}
};

注：左闭右开需要仔细分析最后 start 和 end 究竟是什么，通过循环不变量和最终的 l 和 r 的位置进行分析

收获：

学会了二分查找的左闭右开，左闭右闭，左开右开的写法，虽然卡哥没有讲解左开右开，我看灵神的做法，感觉左开右开可能更简单一些，分析的少一点
之前不太清楚到底返回什么，是 l 还是 r 还是 l - 1什么的，现在清楚了，学会用循环不变量进行分析，分析最后 l 和 r 的位置，进而分析最终到底要返回什么
对于左开右开区间，最终l + 1 == r
对于左闭右开区间，最终l == r
对于左闭右开区间，最终l == r + 1