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

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

文章讲解：代码随想录

视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

【有序数组+无重复元素】可以用二分法

左闭右闭写法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //左闭右闭写法
        int left = 0, right = nums.size()-1;
        while(left<=right){
            // int middle = (left + right)/2;  // 注意两个int相加可能越界
            int middle = left + ((right - left) >> 1);  
            // 计算数组的长度，也就是右边界和左边界之间的距离;
            // 将上述长度除以2的操作，使用位运算 >> 1 来实现。
            // 位运算的右移操作相当于将一个数除以2的n次方（这里是2的1次方，即除以2）
            if(nums[middle] > target){
                right = middle - 1;
            }
            else if(nums[middle] < target){
                left = middle + 1;
            }
            else return middle;
        }
        return -1;
    }
};

左闭右开写法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        size_t numsize = nums.size();
        //左闭右开写法
        int left = 0;
        int right = numsize;
        int middle;
        while (left<right){
            // int middle = (left + right)/2;  // 注意两个int相加可能越界
            middle = left + ((right - left) >> 1);  
            // 计算数组的长度，也就是右边界和左边界之间的距离;将上述长度除以2的操作，使用位运算 >> 1 来实现。
            // 位运算的右移操作相当于将一个数除以2的n次方（这里是2的1次方，即除以2）
            if(nums[middle] > target){
                right = middle;
            }
            else if(nums[middle] < target){
                left = middle + 1;
            }
            else return middle;
        }
        return -1;
    }
};

时间复杂度：O(log n)

1. 每次查找都将问题的规模减半：在二分查找中，每次比较都将搜索范围缩小到原来的一半。这是因为它利用了数组（或有序数据结构）的特性，根据中间元素与目标元素的大小关系，可以确定目标元素位于左半部分还是右半部分，从而将搜索范围缩小一半。

2. 每一次操作都是常数时间：在每次查找中，只需执行一次比较操作来确定目标元素位于哪一半，这是一个常数时间操作，不依赖于数据集的大小。

由于每次查找都将问题规模减半，这导致了二分查找的时间复杂度是对数时间复杂度，即O(log n)，其中n是要搜索的元素的数量（或数据集的大小）。这意味着无论数据集有多大，二分查找都可以在非常快的时间内找到目标元素，因为它以对数级别的速度增长，而不是线性地随数据集大小增加。这使得二分查找成为一种高效的查找算法，特别适用于大型有序数据集。

空间复杂度：O(1)

二分查找都不会随着数据集大小的增加而增加额外的内存消耗，空间复杂度始终保持在O(1)。这使得二分查找成为一种具有高效空间利用率的查找算法，特别适用于在内存受限的环境中运行。

35. 搜索插入位置

题目链接：

文章讲解：

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

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

34. 在排序数组中查找元素的第一个和最后一个位置

题目链接：力扣链接

文章讲解：代码随想录 (programmercarl.com)

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 左闭右闭
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一：target 在数组范围的右边或者左边，此时应该返回{-1, -1}
        if(leftBorder==-2 || rightBorder==-2) return {-1,-1};
        // 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
        if(rightBorder-leftBorder>1) return {leftBorder+1,rightBorder-1};
        // 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
        return {-1, -1};
    }
private:
    // 二分查找，寻找target的右边界（不包括target）
    int getRightBorder(vector<int>& nums, int target){
        int left=0, right=nums.size()-1;
        int RightBorder = -2;  // 记录一下rightBorder没有被赋值的情况
        while(left<=right){
            int mid = left + ((right-left)>>1);
            if(nums[mid]>target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
                RightBorder = left;
            }
        }
        return RightBorder;
    }

    int getLeftBorder(vector<int>& nums, int target){
        int left=0, right=nums.size()-1;
        int LeftBorder = -2;  // 记录一下rightBorder没有被赋值的情况
        while(left<=right){
            int mid = left + ((right-left)>>1);
            if(nums[mid]<target){
                left = mid + 1;
            }
            else{
                right = mid - 1;
                LeftBorder = right;
            }
        }
        return LeftBorder;
    }
};

27. 移除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        for (int i=0; i<len; i++){
            if (nums[i]==val){
                len--;
                for (int j=i; j<len;j++){
                    nums[j] = nums[j+1];
                }
                i--;
            }
        }
        return len;
    }
};
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
        // 定义快慢指针
        // 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
        // 慢指针：指向更新 新数组下标的位置
        int slow=0;
        for (int fast=0; fast<nums.size(); fast++){
            if (nums[fast]!=val){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};
// 时间复杂度：O(n)
// 空间复杂度：O(1)