代码随想录算法训练营第一天|二分搜索移除元素

75 阅读 0 评论 50 点赞

我是靠谱客的博主酷酷小松鼠，最近开发中收集的这篇文章主要介绍代码随想录算法训练营第一天|二分搜索移除元素，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

### 二分查找：

前提条件：数组为有序数组，同时题目强调数组没有重复元素

两种写法：

1.左闭右闭写法

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

2.左闭右开写法：

```c++
class Solution {
public:
int search(vector<int>& nums, int target) {
//二分法左闭右开写法
int left=0;int right=nums.size();int middle=0;
while(left<right){
//为什么没有等号，左闭右开的写法就是，右边边界的数是娶不到的，是开区间
middle=(left+right)/2;
if(nums[middle]>target){
right=middle;//这里right=middle的原因也是保持左闭右开，right取不到
}else if(nums[middle]<target){
left=middle+1;
}else{
return middle;
}
}
return -1;
}
};
```

区别：左闭右闭和左闭右开最大的区别就在于区间上，左闭右闭的作用边界值都可以取到，但是左闭右开的右边边值是取不到的。

区别在代码上的体现：左闭右开的代码right=nums.size()；这个right的值是取不到的，while循环中为什么没有right=left的情况就是因为right的值是取不到的，所以right=left=middle的这次循环没有任何意义(因为nums[right]在此之前已经判断过了)。

重点：不管是左闭右开还是左开右闭，我们的循环都需要坚持这个原则。

只要下次看到有序数组都可以考虑是否可以使用二分查找，同时还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一

### 双指针法：

#### 移除元素：给定数val,把数组中值为val的元素全部删除

```c++
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
//双指针写法
int fast=0;int slow=0;
for(fast;fast<nums.size();fast++){
if(nums[fast]!=val){
nums[slow++]=nums[fast];
}
}
return slow;
}
};
```

心得：之前写过类似的题，不过当时是新开辟了一个数组，将不用删除的数放到新的数组中去，虽然时间复杂度与双指针法相比同为o(n)，但是空间上多了o(n).