画图理解算法第1天 数组Part01| 704. 二分查找、27. 移除元素

704 二分查找

力扣题目连接：https://leetcode.cn/problems/binary-search/
代码随想录讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

题目

image.png

分析

二分查找有左闭右闭[left, right]和左闭右开[left, right)两种方式。

left、right 为索引

对于左闭右闭方式

输入 nums = [-1,0,3,5,9,12] , target = 5

image.png

image.png

初始化之后，要利用二分查找法来找到对应的target目标数字，二分查找顾名思义就是一分为二，所以使用mid指针来表示，mid = (right-left)/2+left 这个就是找到left指针和right指针所对应的二分后的中间位置。

mid = (right-left)/2+left 这样计算是为了避免数值溢出
如果使用 mid = (right+left)/2 的话，right+left的值在int类型下可能存不下导致溢出

此时找到了左右指针的中间位置即mid所指。现在需要判断nums[mid]的值与target值的大小，从而确定是left指针移动还是right指针移动。
nums[mid]是等于3的，是小于target的值5，所以索引小于等于mid对应的数值肯定都是小于target的，肯定不存在5这个目标数，所以left指针要移动到mid+1的位置

image.png

此时left指针和right指针又是新一轮的新值。重复上述操作，再次找到mid的值，即mid = (right-left)/2+left 即 mid等于4

image.png

再次判断nums[mid]与target的大小，显然nums[mid]的值为9，target的目标值为5，即nums[mid]大于target，由于数组里的存数都是从小到大排序的，所以索引大于等于mid对应的数组值都是比target目标值5大的，所以需要将right指针移动到mid-1位置

image.png

left指针和right指针都调整好了之后，又重复上述操作计算mid值，即mid的值为3

image.png

此时将nums[mid]与target进行比较，发现nums[mid]等于target，即找到了目标值的索引，所以直接return mid就行。如果找不到肯定会出现left>right的情况，则直接退出循环，返回-1即可。

代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        int mid = 0;
        while(left <= right) {
            mid = (right - left) / 2 + left; // 计算mid
            if(nums[mid] < target) { // 将mid所指的数值与target进行比较
                left = mid + 1; // 调整left
            }else if (nums[mid] > target) { // 将mid所指的数值与target进行比较
                right = mid - 1; // 调整right
            }else{
                return mid; // 找到了直接return
            }
        }
        return -1; // 未找到返回-1
    }
};

27. 移除元素

力扣题目连接：https://leetcode.cn/problems/remove-element/description/
代码随想录讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html

对于移除元素暴力解就是双for循环。但是这道题要学会双指针来求解。需要剔除的数被后面的不需要进行剔除的数进行覆盖的思想，来剔除目标数字。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int idx = 0; // 用于记录下一个需要填充值的索引位置
        int len = nums.size(); // 整个数组长度
        for(int cursor = 0; cursor < len; cursor++){ // cursor的作用就是从头到尾遍历一遍数组
            if(nums[cursor] == val) { // 如果当前遍历的数与需要剔除的数一致，说明这是需要被剔除的数，则不需要存到nums中了，直接跳过就行
                continue;
            }
            nums[idx++] = nums[cursor]; // 如果不一致的话，就是需要保留的数字，那么这个数字就需要填充到idx位置，然后idx再往后移一个位置
        }
        return idx; // 最后idx就是剔除后的数组长度
    }
};