代码随想录打卡第一天

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

注意二分查找应用的条件 单调或者局部单调的数据或者别的数据结构。二分法要定义区间的左边界和有边界。并且根据区间的左右边界的开闭设计的算法也不同。

题目是单调递增的数据。解法注意是当中间节点不符合目标时，要更新查找区间。首先while()循环，既然left<=right；可以取等号，那么一定是左闭右闭的区间。接下来找到中间节点，当中间结点小于目标时，证明目标节点在右侧，此时要更新左边界，left=middld+1是因为nums[middle]已经查找过middle结点了，所以跳过他；当中间节点大于目标时，证明目标在左侧，此时要更新右边界，为什么是right=middle-1；同样的，首先是因为已经查找过这个middle节点，不需要再查一遍了，并且因为是右闭的区间。

左闭右开的解法

public:int search(vector<int>& nums, int target) {int left=0;//左边界int right=nums.size();//右边界while(left<right){int middle=(left+right)/2;if(nums[middle]<target){left=middle+1;}else if(nums[middle]>target){right=middle;}else{return middle;}}return -1;}
};

【经典排序算法】二分查找法 (动图演示 + C 语言代码实现)_二分查找动图-CSDN博客

双指针法

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

 暴力解法就是两次for循环。双指针法就是用一次就行了。

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

首先如果nums[fast]!=val,原地更新，比如所有的元素中都没有我们要找的，那么遍历一遍之后数组还原来的数据。

如果nums[fast]==val，证明找到了我们想要的元素，那么此时slow和fast指向的都是这个想要替代的元素，那么slow不变，fast继续+1，继续寻找下一个我们不想替换的元素，如果找到不是我们想要的元素，那么就让slow索引下的元素等于fast索引下的元素，也就是用后面不是想要替代的元素去替代我们想要替代的元素。

最后fast遍历完一次,slow就是剩下的元素个数。

依照此法已经解决的题目
26. 删除有序数组中的重复项 - 力扣（LeetCode）