2026.01.28 第一天
704 二分查找
一上来边界逻辑没搞清楚，所以做的有些头疼
本题关键在于边界的确定和更新，可以将数组看做一个区间，利用区间的严谨的数学定义进行边界值的更新。
写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
二分法可以使用while循环配合数组是否合法的条件，即是否满足left<=right或left<right判断是否结束查找。
这里直接复制了Carl的讲解和图片
左闭右闭[left, right]
while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
C++实现代码如下：
class Solution {
public:int search(vector<int>& nums, int target) { //Carl左闭右闭写法int left = 0;int right = nums.size() - 1;while(left <= right) {if(nums[(left + right) / 2] == target) {return (left + right) / 2;}else if(nums[(left + right) / 2] < target) {left = (left + right) / 2 + 1;}else if(nums[(left + right) / 2] > target) {right = (left + right) / 2 - 1;}}return -1;}
};
左闭右开
while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
27 移除元素
本题使用了快慢指针的思想，在黑马课程中见过本题，所以一下子就写出来了~
class Solution {
public:int removeElement(vector<int>& nums, int val) {int left = -1; // 这里的慢指针指向的是已经更改的元素，同时也代表已经更改的元素的数量减1int right = 0;while (right < nums.size()) {if (nums[right] != val) {left++;nums[left] = nums[right];}right++;}return left + 1;}
};
https://file1.kamacoder.com/i/algo/27.移除元素-双指针法.gif
在知乎上找了一段关于快慢指针的描述：
快慢指针方法也被称为Hare& Tortoise算法，该算法会使用两个在数组（或序列/链表）中以不同速度移动的指针。该方法在处理循环链表或数组时非常有用。
该算法的应用场景：处理链表或数组中的循环的问题；找链表中点或需要知道特定元素的位置
977 有序数组的平方
由于可能存在负数，导致直接平方之后数组元素的顺序可能会发生变化，因此需要考虑怎样在保持时间复杂度为O(n)的条件下让数组变得有序。
由于要返回新的数组，考虑到旧数组平方之后最大值在两端，因此采用双指针法，用左右两个指针指向当前旧数组中两端的元素，其中一定存在平方之后最大的元素，比较后得到较大的一个，放入新数组的最后即可，下面是C++实现：
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> sorted(nums.size());int left = 0;int right = nums.size() - 1;for (int i = nums.size() - 1; i >= 0; i--) {if (nums[left] * nums[left] <= nums[right] * nums[right]) {sorted[i] = nums[right] * nums[right];right--;} else {sorted[i] = nums[left] * nums[left];left++;}}return sorted;}
};