📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：练题
🎯长路漫漫浩浩，万事皆有期待
文章目录
二分查找
● 什么是区间不变量？ 比如 区间取左闭右闭的话 那么每次区间二分 范围都是新区间的左闭右闭 后面做判断时 要一直基于这个左闭右闭的区间，其实区间定义成开或者闭都没有什么关系 只是要明确每次收缩范围后 范围内的元素是哪些 注意会不会漏掉边界
● 需要注意二分的几种情况
○ 当l = 0, r = n的时候因为r这个值我们在数组中无法取到,while(l < r) 是正确写法
○ 当l = 0, r = n - 1的时候因为r这个值我们在数组中可以取到,while(l <= r) 是正确写法
主要看能不能取到这个值
● 主要是对左闭右开[left<=right)，左闭右闭(left<right)区别和怎么更新left,right的值有一定误解
由于数组元素为有序排列，我们仅需要确定搜索的左右边界。在该题中存在两种情况，即右边界的选择：
解决方法一：左闭右开[left<=right)，right = nums.size() - 1;
在这种情况下，每次的搜索区间为 [left, right] 即左闭右闭区间，此时对应的循环条件应为 while (left <= right)，终止条件为 left == right + 1，即 [right + 1, right]，此时区间为空，故循环终止，程序返回 -1 即可；
class Solution {
public://这种情况是前闭后闭的情况
int search(vector<int>& nums, int target) {
int left=0;int right=nums.size()-1;
while(left<=right)
{
int mid=(left+right)/2;
if(nums[mid]<target)left=mid+1;
else if(nums[mid]>target)right=mid-1;
else return mid;
}
return -1;
}
};
由于mid被判断不是目的值，故两边界取的是mid的前一个值(改变右边界时)或mid的后一个值(改变左边界时)，这样写的好处是把已经确定不在判断范围内的值给去掉，所以才写成从mid的前一个数或后一个数判断，而判断区间里由于两边区域都是闭区间所以可以带等于号。
易错：注意mid要放在while里面，mid本身是一直变化的
解决方法二：左闭右闭(left<right)，right = nums.size();
对于这种情况，由于数组，此时的搜索区间为[left, right)即左闭右开区间，此时对应的循环条件为 while (left < right)，终止条件为 left == right，即 [right, right]，此时区间内仅存一个元素 right，直接返回 -1 是不对的，还需对该索引进行判断。
class Solution {
public://这种情况是前闭后开的情况
int search(vector<int>& nums, int target) {
int left=0;int right=nums.size();
while(left<right)
{
int mid=(left+right)/2;
if(nums[mid]<target)left=mid+1;
else if(nums[mid]>target)right=mid;
else return mid;
}
return -1;
}
};
第二种方法是左闭右开的情况，由于两侧边界不能相等，故判断区域不带等于号，右开：虽然右边界更改时，也不取mid值，但是由于右边区间是开区间，所以写成right=mid；是可行的，等于mid但是取不到
● 二分的最大优势是在于其时间复杂度是O(logn)，因此看到有序数组都要第一时间反问自己是否可以使用二分。
● 其实二分还有很多应用场景，有着许多变体，比如说查找第一个大于target的元素或者第一个满足条件的元素，都是一样的，根据是否满足题目的条件来缩小答案所在的区间，这个就是二分的本质。
注意:二分的使用前提：有序数组
● 关于二分mid溢出问题：
-
mid = (l + r) / 2时，如果l + r 大于 INT_MAX(C++内，就是int整型的上限)，那么就会产生溢出问题（int类型无法表示该数）
-
所以写成 mid = l + (r - l) / 2或者 mid = l + ((r - l) >> 1) 可以避免溢出问题
● 对于二进制的正数来说，右移x位相当于除以2的x几次方，所以右移一位等于➗2，用位运算的好处是比直接相除的操作快
移除元素
这道题主要是考察选手对于数组方面的掌握，
分两种方法 ：一种是常见的暴力求解O（N*2），另一种则是稍微有些巧妙的双指针遍历O（N）
暴力求解
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size=nums.size();
for(int i=0;i<size;i++)
{
if(nums[i]==val)
{
for(int j=i+1;j<size;j++)
nums[j-1]=nums[j];//避免溢出的处理方法
size--;
i--;
}
}
return size;
}
};
暴力求解主要是要注意size来记录返回数组的个数，每次找到val值后，i - -，这是因为找到val后val后的每个值都会向前一位，来挤掉之前的val值，让i - -，是从当前发现的val的下一个值来开始遍历，以免有落下的数没有判断。
双指针遍历
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int fast=0,slow=0;
for(;fast<nums.size();fast++)
if(nums[fast]!=val)
nums[slow++]=nums[fast];
return slow;
}
};
slow、fast一开始都指向原点，然后fast向后走，直到找到val，开始做替换并且slow开始指向下一个位置，当fast走到最后，就说明所有的元素都被遍历完了，此时的slow值，就代表数组元素个数。
关于移除元素
● 快指针可以理解成在旧数组中找非目标元素，然后赋值给慢指针指向的新数组，虽然都指向一个数组
● 关于二分法和移除元素的共性思考
都是在不断缩小 left 和 right 之间的距离，每次需要判断的都是 left 和 right 之间的数是否满足特定条件。对于「移除元素」还可以理解为，拿 right 的元素也就是右边的元素，去填补 left 元素也就是左边的元素的坑，坑就是 left 从左到右遍历过程中遇到的需要删除的数，因为题目最后说超过数组长度的右边的数可以不用理，所以是以 left 为主，这样可能更直观一点。
● fast < nums.size() 和 fast <= nums.size()-1 没什么区别，那为什么第二个会在空数组时报数组越界的错误？
因为vector的size()函数返回值是无符号整数，空数组时返回了0，再减个1会溢出
总结：
今天的两道题其实在很久之前做过，但当时没有真正理解里面的细节问题，现在总算理解了。接下来，我们继续进行算法练习·。希望我的文章和讲解能对大家的学习提供一些帮助。
当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~
