代码随想录算法训练营第一天|[704. 二分查找]|[27. 移除元素]

c

代码随想录算法训练营第一天|704. 二分查找 |27. 移除元素

视频讲解

文档讲解

---

704 . 二分查找

思路：首先必须是已经排好序的数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size();            //定义区间左右限
        while(nums[l]<=nums[r]){        //中止条件，l被发现和r重叠
            int mid= l+(r-l)/2;             //上取整取mid
            if(nums[mid]<target){           
                l=mid;
            }
            else if(nums[mid]>target){
                r=mid;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
};

左闭右闭

和代码随想录推荐写法思路一致

第一次自己写的代码过了一个测试用例。

进行debug

发现错误点是数组边界没有-1，导致数组越界访问。

提交力扣后产生报错

找出循环条件书写有误

while(nums[l]<=nums[r]) 	//错误--数值
/*
1. 越界访问：
问题：如果目标值不在数组中，使用while (nums[l] <= nums[r])作为循环条件可能会导致l或r超出数组的合法索引范围。当l或r成为无效索引时，尝试访问nums[l]或nums[r]将会导致未定义行为，可能是越界访问，这是非常危险的。

原因：在二分搜索中，如果目标值不在数组中，l和r会继续移动直到它们超出数组的边界或者成为无效的，这个时候使用它们来索引数组就会出现问题。

2. 无法正确终止：
问题：即使l和r都是有效索引，如果目标值不在数组中，使用nums[l] <= nums[r]作为循环条件可能会导致循环无法正确终止。这种情况下，算法可能会陷入无限循环，或者在错误的位置停止。

原因：在某些情况下，尽管l和r已经缩小到一个很小的范围，但如果目标值不在这个范围内，nums[l]可能仍然会小于或等于nums[r]，导致循环无法退出。
*/
while(l<r)		//正确   --直接使用下标访问

更改后正确

左闭右开

左闭右开法的主要思路

区间被定义为左闭右开，即[left, right)。这意味着考虑的元素包括left索引处的元素，但不包括right索引处的元素。

当我们说left == right时，在区间[left, right)中实际上没有任何元素。这是因为left和right指向同一个位置，而由于区间是左闭右开的，这个位置的元素不被包括在内。所以，当left == right时，区间是空的，这意味着已经没有更多的元素可以检查，目标元素要么已经找到，要么不在数组中。

在二分搜索中使用while (left < right)而不是while (left <= right)有以下几个原因：

1. 防止无限循环： 如果使用<=，那么当left和right相等时，循环仍然会执行。但是，由于没有元素可以检查，如果没有适当的退出条件，这可能会导致无限循环。
2. 简化逻辑： 使用左闭右开的区间可以简化更新left和right指针的逻辑。例如，在上述代码中，当nums[middle] < target时，可以安全地将left设置为middle + 1，因为我们知道middle处的元素不是目标，并且不会被包括在新的搜索区间内。
3. 一致性和错误预防： 使用左闭右开的区间有助于保持代码的一致性，并减少因边界情况处理不当而引入错误的机会。

因此，在这段代码中，while (left < right)确保了只要区间内有元素可供检查，循环就会继续进行。一旦left等于right，区间变为空，循环停止，这意味着查找要么成功，要么目标元素不在数组中。这种方法是二分搜索算法中处理边界和确保效率的一个典型和优雅的方式。

在代码上稍作修改就可AC

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size();
        while(l<r){      //左闭右开
            int mid=l+(r-l)/2;
            if(nums[mid]==target){
                return mid;
            }
            else if (nums[mid]<target){
                l=mid+1;
            }
            else {
                r=mid;
            }
        }
        return -1;
    }
};

总结

本题三个注意点：

1. 循环条件是<还是<=
2. 左闭右开区间和左闭右闭区间的定义，在左闭右开区间的情况下，r是要往右多数一位的
3. mid越界判断问题mid=l+(r-l)/2; --这是一个经典的求中点的算法，需要牢记

27.移除元素

理论基础

vector.earse 是O(n)操作 不是O1操作

暴力解

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
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];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

第一次测试暴力解逻辑错

错误原因，只考虑了把=val的元素挪到后面，并没有从原地覆盖掉

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){
                nums[i]=nums[size-1];
                size --;
            }
        }
        return size;
    }
};

更改思路

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

把=val的放到后边，前面!=val的进行处理

双指针法

普通双指针

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

双向指针法

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int LeftIndex=0;
        int RightIndex=nums.size()-1;
        while(LeftIndex<=RightIndex){
            while((LeftIndex<=RightIndex)&&(nums[LeftIndex]!=val)){
                ++LeftIndex;
            }
            while((LeftIndex<=RightIndex)&&(nums[RightIndex]==val)){
                --RightIndex;
            }
            if(LeftIndex<RightIndex){
                nums[LeftIndex++]=nums[RightIndex--];
            }
        }
        return LeftIndex;
    }
};

总结

第一天正式开刷力扣，两道题研究了多种解法总共耗时三个小时，收获满满。