今日任务：

1. 数组理论基础
2. LeetCode704 二分查找
3. LeetCode27 移除元素

今日心情：今天第一天，万事开头难，终于是赶在睡之前写完了。还想写多个语言版本帮助自己熟悉新语言来着，脑子真是太困了。想想明天的满课就心累。最后祝自己能够找到想去的暑期实习吧。

资料来源：

数组理论基础

704. 二分查找

27. 移除元素

1 数组理论基础

（只补充之前没了解过的部分）

1. 二维数组在内存中的存储方式随语言不同而不同。C++的二维数组和一维数组是一样的，按顺序排列；而Java的二维数组，每个一维数组之间都是不相连的，由最上层的数组存储指向这些一维数组的地址。

（实在不想自己制图了，但是看图理解确实更快😂）

2 LeetCode704 二分查找

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

有一说一，我一开始看到这题以为能秒杀的，真的。

在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）、对数搜索算法（英语：logarithmic search algorithm），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找的重点在于，如何在代码中规定查找的范围。按查找范围划分，分为左闭右闭区间和左闭右开区间。以下为二分查找代码的框架，出现问号的地方就是要根据区间不同而填充的地方：

python
from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        right = 0
        left = ?
        while right ? left:
            middle = int((right + left) / 2)
            if nums[middle] == target:
                return middle
            elif target < nums[middle]:
                left = ?
            elif target > nums[middle]:
                right = ?
        return -1

1. 左闭右闭区间

如果在左闭右闭区间进行搜索，那么就意味着right和left这两个变量都是要纳入搜索范围的，所以在修改right和left的时候，都不应该等于middle，因为就是在middle不是target的情况下，才需要修改right和left。同理，while条件也应该是right <= left，因为在左闭右闭区间下，left = right是合理的。

python
from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        right = 0
        left = len(nums) - 1
        while right <= left:
            middle = int((right + left) / 2)
            if nums[middle] == target:
                return middle
            elif target < nums[middle]:
                left = middle - 1
            elif target > nums[middle]:
                right = middle + 1
        return -1

2. 左闭右开区间

根据左闭右闭区间举一反三，如果在左闭右开区间进行搜索，那么就意味着right在搜索范围里，而left不在搜索范围里，所以在修改right和left的时候，right不应该等于middle，而left可以。同理，while条件也应该是right < left，因为在左闭右开区间下，left = right是不合理的。

python
from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        right = 0
        left = len(nums)
        while right < left:
            middle = int((right + left) / 2)
            if nums[middle] == target:
                return middle
            elif target < nums[middle]:
                left = middle
            elif target > nums[middle]:
                right = middle + 1
        return -1

3 LeetCode27 移除元素

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

第一次做直接过了，做的时候想着想着才意识到这何尝不是另一种双指针法，然后看了之后才发现真的双指针法确实方便多了（。

python
from typing import List

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        first = 0
        length = len(nums)
        if length == 0:
            return 0
        last = length - 1
        while first <= last:
            if nums[first] == val and nums[last] != val:
                nums[first] = nums[last]
                length -= 1
                first += 1
                last -= 1
            elif nums[first] != val:
                first += 1
            elif nums[first] == val and nums[last] == val:
                last -= 1
                length -= 1
        if first == 0:
            nums.clear()
        return length

双指针法：两个指针一起在数组中循环，由快指针寻找不是val的值，找到之后就存到慢指针处，然后两个指针一起+1；如果找到的是和val相等的值，那么快指针+1，慢指针不动即可。最后循环完成，返回慢指针的位置即可。

python
from typing import List

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast = 0
        low = 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[low] = nums[fast]
                low += 1
            fast += 1
        return low