day1 - 数组part01

力扣704. 二分查找

思路：假如有n个数，数组下标就是0到n-1，那么第一次从n/2开始找

如果这个数比目标数大，说明目标数在左边，于是从0到中间边界找。

如果这个数比目标数小，说明目标数在右边，于是从中间边界+1到n-1找。

为了明确中间边界是多少，举个例子：

假如数组是：0,1,3,5,6,7,8; target = 7;

数组大小是7，第一次从7/2=3开始查找，也就是从5开始，找到5后，发现7比5大， 那么要从5的下一位到末尾也就是下标6。也就是说如果找的数在右边就从下一位到末尾。

假如target=1呢，第一次还是从下标3开始找，也就是5开始，发现5比目标数1大，那么从0到5的上一位开始找。

上面是数组长度为奇数的情况那么如果长度为偶数呢？

比如数组是：0,1,3,5,6,7,8,9; target = 8

数组大小是8， 从4开始找，找到6，发现8比6大，于是从下一位到末尾查找。

由此可以发现，这和数组大小的奇偶性质没有关系。

于是可得逻辑

if (nums[cur] > target)
{
    right = cur - 1;
}
if (nums[cur] < target)
{
    left = cur + 1;
}

接下来写代码

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

代码逻辑比较简单，提交！

OH, No!

没有ac，提示用例是只有一个数的数组。

为什么没通过，思考一下如果只有两个数的数组0, 1，目标值是1

根据代码逻辑，开始值查找的是0，不是目标值，下一个left为1，此时right也是1，循环结束。

因此应该把while循环的条件改为小于等于

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

成功ac！

此题除了改动while循环条件，也可以一开始就将right设置为nums.size()，这样相当于用于比真实的下标大1，此时while循环条件就可以填小于。

因此第一种解法，称之为左闭右闭区间，第二种解法称之为左闭右开区间！

力扣27. 移除元素

思路：快慢指针，一个快指针负责遍历数组，如果找到数值不是val的数，那么把数值赋值给慢指针，然后慢指针移动到下一位。

其实这个思路就是一个萝卜一个坑，快指针负责出去找萝卜，慢指针在家里等着，有萝卜了就把萝卜放进去，然后去下一个坑等着

代码实现：

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

总结

明天面试，这两个等有时间刷。35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置 。代码随想录已经粗略刷过一遍了，这次要深入的刷，尽量把所有解法已经其原理搞懂。