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

---

LeetCode704. 二分查找

这道是标准的二分查找。
关于二分查找，有几个点是值得说的。

1.注意边界值

二分法常见的写法是左闭右闭和左闭右开。
那么问题来了？

1. 请问左闭右闭和左闭右开的初始值left和right分别应该怎么写？
2. 循环的条件在左闭右闭，左闭右开的写法分别是什么？
3. 当target >nums[mid]的时候，left在左闭右闭，左闭右开的写法分别是什么？
4. 当target <nums[mid]的时候，right在左闭右闭，左闭右开的写法分别是什么？
5. 为什么是这样？

---

回答这个问题的关键在于，要理解左闭右闭，左闭右开的含义，说直白点就是
[1,1]和[1,1)是否成立

---

很显然，在左闭右闭的时候，[1,1]是可以成立的，因为闭区间是包含的意思
在左闭右开的时候，[1,1)显然不能成立的，因为做不到同时对1个数既包含又不包含。下面请看代码。

左闭右闭

def binary_search(nums, target):
	#因为是左闭右闭，所以右边就等于len(nums)-1
    left = 0
    right = len(nums) - 1
	#这里就是第一个点，左闭右闭中，他们是可以相等的
    while left <= right:
        mid = (left+right)//2
        if nums[mid] == target:
            return mid
            #下面就是第二点，因为我们是左闭右闭，mid我们已经判断过不是了
            # 所以，在左闭右闭中，我们要把mid给排除
        elif target < nums[mid]:
            right = mid -1
        elif target > nums[mid]:
            left = mid + 1
    else:
        return -1

左闭右开

def binary_search(nums, target):
	#因为是左闭右开，所以右边就等于len(nums)
    left = 0
    right = len(nums)
	#这里就是第一个点，左闭右开中，他们是不能相等的
    while left < right:
        mid = (left+right)//2
        if nums[mid] == target:
            return mid
            #下面就是第二点，因为我们是左闭右开，mid我们已经判断过不是了
            # 所以，在左闭右开中，left或right要等于mid
        elif target < nums[mid]:
            right = mid
        elif target > nums[mid]:
            left = mid + 1
    else:
        return -1

2.整数溢出问题

在上面的代码中，如果是其他语言还存在一个问题就是整数溢出问题。这个问题通常发生在我们需要查找的数据规模很庞大的地方。
比如我们有个right = MaxInt-1的数据，需要查找的tag在后半段，那么left+right 百分百会超过int的最大值。

具体的写法就是

mid = left + (right-left)//2

这种写法是一定不会溢出的。

---

常见bug

在二分法里面，常见的bug就是死循环了，没有写对范围大概率是要死循环的。
写leetcode这道题的时候，看见时间超时，大概率是死循环了。

---

LeetCode27. 移除元素

---

这道题难度不大，它的精髓有三个
1.对库函数的使用(新手可以作为熟悉库函数来练习)
2.双指针降低时间复杂度。
3.对数组的理解

---

库函数解法

def removeElement(nums, val):
    count = nums.count(val)
    for i in range(count):
        nums.remove(val)
    return len(nums)

暴力解法

def removeElement(nums, val):
    i, l = 0, len(nums)
    while i < l:
        if nums[i] == val:  # 找到等于目标值的节点
            for j in range(i + 1, l):  # 移除该元素，并将后面元素向前平移
                nums[j - 1] = nums[j]
            l -= 1
            i -= 1
        i += 1
    return l

快慢指针

def removeElement(nums, val):
    fast = 0
    slow = 0
    while fast < len(nums):
        if nums[fast] == val:
            fast += 1
            if fast < len(nums):
                nums[slow] = nums[fast]
        elif nums[fast] != val:
            nums[slow] = nums[fast]
            fast += 1
            slow += 1

    return slow

---

总结

卡哥讲题确实能讲到精髓，感觉今天还是有进步的。