代码随想录算法训练营Day 1 | 二分：LeetCode704二分查找、35搜索插入位置、34查找元素第一个和最后一个位置 | 双指针：27移除元素、977有序数组的平方

704.二分查找

模板题
题目链接：https://leetcode.cn/problems/binary-search/代码随想录题解： 704. 二分查找 | 代码随想录
状态：完全掌握三种模板
“一只会code的小金鱼”的分界线思路（左开右开）和卡哥的思路（左闭右开）（左闭右闭）

        这题是模板题，用卡哥的思路很快就写出来了，而且很好记忆；

        我给二分模板定了三要素进行记忆，1.左右初始化；2.while()条件；3.mid是否±1。

        以前自己写二分老是会忘记while（）的条件是left<right还是left<=right？什么时候用left=middle+1还是left=middle，right=middle-1还是right=middle?初始化该用left=0还是left=-1，right=nums.size()还是right=nums.size()-1？

        理解二分的边界是最容易记忆二分的，理解方法是区间不变量原则，小金鱼的思路也可以归到区间不变量原则里。为了方便，我现在定义的数组都是从小到大顺序排序并且数组从0开始。

        区间不变量是指将二分的Left和Right当成区间，同时固定为闭区间还是开区间的不变量。简单来说举个例子：（左闭右开）Left是闭区间，Right是开区间，Left的值是可以取到的，但Right的值无法取到。首先看1.左右初始化：左闭left时数组可以取到left值，所以left=0等于原数组的下标下限，右开right取不到，所以right=nums.size()比原数组的下标上限多1个；2.while()条件：左闭left时数组可以取到left值，右开right时数组取值不到，right不能=left值，所以while(left<right)；3.mid是否±1：左闭left时数组可以取值，此时mid=left+right>>1，nums[mid]<target，left更新，因为mid此时的值已经不符合target了并且是左闭left是可以取到的，所以left不取mid，而是从mid+1开始，所以左闭mid+1。同理，右开right时数组取不到right的值，nums[mid]>target，right更新，mid此时的值不符合target并且右开right的值是取不到的，所以right是可以取到mid。那左闭右闭则left=mid+1，right=mid-1；以此类推左开右开left=mid，right=mid。

        我做了个表格以此类推我的理解原则：

        最后一行是小金鱼的模板，我记忆为两边都是开的情况，是符合我们的区间不变量原则的，同时没有左开右闭这种情况是因为日常开发中都是用的左闭的多。

        下面用左闭右开手撕模板题，模板题是默认了从小到大排列同时没有重复元素的：

class Solution { public: int search(vector<int>& nums, int target) { int left=0,right=nums.size(),middle; while(left<right) { middle=left+(right-left)/2;//防止两个int相加爆int if(nums[middle]==target)return middle; else if(nums[middle]>target)right=middle; else left=middle+1; } return -1; } };

35.搜索插入位置

题目链接：35. 搜索插入位置 - 力扣（LeetCode）
【二分查找 | 妈妈再也不怕我写错二分啦 | 五点七边二分视频补充】 https://www.bilibili.com/video/BV1fA411z7ru/?share_source=copy_web&vd_source=7a3599e572d9e56d7bbfb1f44a9b852d

        这题和上面的模板题变化的地方在于找不到target不是输出-1了，而是插入到原数组去；

我这里使用左开右开来写，使用小金鱼的分界线理论，可以看小金鱼的视频当作卡哥的模板的衍生；我的个人详细理解在下一道题。

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

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

题目链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

思路：【二分查找 | 妈妈再也不怕我写错二分啦 | 五点七边二分视频补充】 https://www.bilibili.com/video/BV1fA411z7ru/?share_source=copy_web&vd_source=7a3599e572d9e56d7bbfb1f44a9b852d

        我的个人思路，把mid当成分界线，左边left都是小于target，右边right都是大于等于target的，所以分界线右边第一个元素就是target第一次出现的位置，即此时right的下标；

        同理当我的左边都是小于等于target的数，右边都是大于target的数，那分界线左边第一个元素就是target最后一次出现的位置，即此时left的下标；

手撕代码如下，用的左开右开：

class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { if(nums.empty())return{-1,-1};//当数组是空的时候直接结束输出-1，-1 int l1,r1,l2,r2; int ans1,ans2; l1=-1;l2=-1;r1=nums.size();r2=nums.size(); while(l1+1!=r1) { int mid=l1+(r1-l1)/2; if(nums[mid]>=target)r1=mid; else l1=mid; } if(r1<nums.size()&&nums[r1]==target)ans1= r1; else return{-1,-1}; while(l2!=r2-1) { int mid=l2+(r2-l2)/2; if(nums[mid]>target)r2=mid; else l2=mid; } if(nums[l2]==target)ans2=l2; // else ans2= -1; 这行可写可不写，因为第一个出现位置找不到就肯定找不到最后一个出现位置 return {ans1,ans2}; } };

27.移除元素

题目链接：https://leetcode.cn/problems/remove-element/

代码随想录：27. 移除元素 | 代码随想录

思路：双指针（快、慢指针）

        这题在力扣是可以暴力写的，但时间复杂度是O(n*n)；

        用双指针可以只用一层for循环，时间复杂度到O(n)；

        由于数组在内存上是一段连续的地址，所以是不存在删除的，只能用后面的元素覆盖掉实现“删除”。所以我们可以用两个指针进行更新数组，快指针fast用于指向不删除的元素，慢指针slow指向我们的新数组，将fast指向的值给slow即可完成更新。具体代码如下：

class Solution { public: int removeElement(vector<int>& nums, int val) { int size = nums.size(); for(int fast=0,slow=0;fast<nums.size();fast++) { if(nums[fast]!=val) { nums[slow++]=nums[fast]; } else size--; } return size; } };

Tips：力扣上的超过百分之多少的人当玩具就行了，多交几次一样的代码也可超过百分百；

977.有序数组的平方

题目链接：977. 有序数组的平方 - 力扣（LeetCode）

代码随想录题解：977.有序数组的平方 | 代码随想录

思路：双指针（头、尾指针）

        暴力写法可以直接全部平方之后再sort排序，但因为sort复杂度是O(nlogn)的，还能再优化。

        用空间换时间，再开一个新数组，因为存在负数的平方是大于正数的，而且原数组是有序排列的，所以可以头尾各设计一个指针，平方值大的更新在新数组的末尾，这样只用一次循环，代码时间复杂度O(n)，代码如下：

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

太忙了，第二天才完成第一天的内容，二分还是很建议大家琢磨透再写的，很重要的算法。