算法刷题Day1 | 704.二分查找、27.移除元素

• 🙋‍♂️ 作者：海码007
• 📜 专栏：算法专栏
• 💥 标题：代码随想录算法训练营第一天 | 704.二分查找、27.移除元素
• ❣️ 寄语：书到用时方恨少，事非经过不知难！

0 引言

1 二分查找

• 🎈 文档讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
• 🎈 视频讲解：https://www.bilibili.com/video/BV1fA4y1o715/
• 🎈 做题状态：有思路但是不清晰，对于循环的判断条件还有区间的变换存在疑惑（这些就是二分法的易错点）

1.1 我的解题

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

分析：没有标准答案简洁，原因是我的 left 和 right 赋值思路不对（相差1）。我是判断完大小后直接将 left 和 right 直接赋值 middle 。其实这样不对，因为 middle 的值已经判断过了，不需要再将这个索引值包含在 [left, right]区间中。

1.2 修改后

所以需要将代码进行如下修改，这样可以省去很多其他条件的判断。

class Solution {
public:int search(vector<int>& nums, int target) {int left, right, middle;left = 0;right = nums.size() - 1;while (right >= left){middle = (right - left) / 2 + left;cout << "middle = " << middle << endl;if (target == nums[middle]){return middle;}else if (target > nums[middle]){left = middle + 1;}else{right = middle - 1;}}return -1;}
};

1.3 总结

看到顺序排列的数组，就可以联想到二分法

二分法易错点：

1. while循环条件：
   • while(left <= right)
   • while(left < right)
2. left和right的赋值
   • left = middle+1; right = middle -1;
   • left = middle+1; right = middle;

其实while和left、right的赋值是对应的，

• 使用while(left <= right)循环时，left = middle+1; right = middle -1;
• 使用while(left < right)循环时，left = middle+1; right = middle;

因为当 left = middle+1; right = middle -1; left和right都把已经判断过的 middle 索引给排除在区间之外了，所以循环遍历的条件需要包括 left和right ，也就是 左闭右闭 区间。
当 left = middle+1; right = middle; 可以发现right没有把已经判断过的 middle 索引给排除在区间之外，所以循环条件不需要包括 right 的索引， 也就是 左闭右开 区间。

---

使用左闭右闭 区间时，最后left和right的结果是什么，当 left等于right的时候（此时middle也等于left和right），还会再执行一次循环，当nums[middle] > target 时 right = middle+1; 也就是说right又往右移动了一位。当nums[middle] <= target 时，right保持原位置不变。
这个特性可以帮助 35.搜索插入位置 这道题理解。

2 移除元素

• 🎈 文档讲解：https://www.programmercarl.com/
• 🎈 视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP/?vd_source=d499e7f3a8e68e2b173b1c6f068b2147
• 🎈 做题状态：暴力求解没太大难度，快慢指针有需要理解的地方

2.1 暴力求解

一开始用暴力求解，输出答案不对，代码如下。我的的输出结果总是不能把最后一位元素给移除，后面发现遍历时没有遍历到最后一个元素。i < arraySize - 1 判断条件没写好，应该是 i < arraySize 或者 i <= arraySize - 1 。这个易错点以后要注意！！！

---

class Solution {
public:int removeElement(vector<int>& nums, int val) {int arraySize = nums.size();for (int i = 0; i <= arraySize - 1; i++){cout << "i = " << i << endl;if (nums[i] == val){for (int j = i; j < arraySize - 1; j++){nums[j] = nums[j + 1];}--arraySize;--i;}}return arraySize;}
};

2.2 双指针法（快慢指针）

快指针：遍历元素值
慢指针：存储新数组的元素值

思路：
遇到等于目标元素的值就跳过，遇到不等于目标元素的值就进行赋值。借助两个索引值（fastIndex和slowIndex）实现，fastIndex遇到目标元素就跳过，此时slowIndex不动，因为目标元素不需要存储。然后遇到不等于目标元素的值就进行赋值。此时是fastIndex在前面探路，然后slowIndex将fastIndex探路得到的结果进行保存。

因为数组的存放是顺序的，所以只有在遇到不等于目标元素的值时，slowIndex才会增加一，然后将非目标值保存下来。

fastIndex从头遍历到尾，所以直接用fastIndex作为遍历元素，条件为 fastIndex < nums.size() 即可。然后当 fastIndex 所指元素不等于目标元素值时，此时将 fastIndex 的值赋值给slowIndex 处。并且slowIndex加一。由此可知 nums 数组中有多少个不等于目标值的元素（个数就是slowIndex）。

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