代码随想录算法训练营第一天 | 704.二分查找、35.搜索插入

题目704.二分查找（两个前提：1.有序数组；2.无重复元素）

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

关键点：
1. 区间搜索的时候要明确区间定义：左闭右闭[]还是左闭右开[)？左开右闭比较少见。。
2. 边界处理，left<right还是left<=right,right=middle还是right=middle-1
3. 循环中根据区间定义做边界处理，就是循环不变量规则：在while循环中坚持一个区间，区间即不变量

# 左闭右闭，合法区间的话left可能等于right
left = 0, right = numsize - 1, target
while(left <= right)：
    middle = (left + right)/2
    if nums[middle] > target:
        right = middle - 1
    else if nums[middle] < target:
        left = middle + 1
    else
        return middle
return -1

# 左闭右开， 合法区间的话left要小于right
left = 0, right = numsize, target
while(left < right)：
    middle = (left + right)/2
    if nums[middle] > target:
        right = middle
    else if nums[middle] < target:
        left = middle + 1
    else
        return middle
return -1
                               

题目35.搜索插入位置

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right:
            middle = (left + right) // 2
            if nums[middle] > target:
                right = middle - 1
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return left #假如原数组没有该target，left位置为要插入的位置

题目27.移除元素

1. 限制O(1)的空间复杂度
2. 

## 暴力解法

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, j = 0, len(nums)
        while i < j:
            if nums[i] == val:
                for k in range(i+1, j): #range右边是开区间，因此取不到，所以j=len(nums)而不是len(nums)-1
                    nums[k-1] = nums[k]
                i -= 1 #因为元素被删掉之后，还要从当前位置开始查找，因此这里-1
                j -= 1
            i += 1
        return j

## 双指针法
1. 用双指针代替一层for循环，相比于暴力解法的O(n^2)的时间复杂度，双指针可降低到O(n)的时间复杂度
2. 快指针用来寻找新数组所需要的元素
3. 慢指针用来定位要更新的位置


slow = fast = 0
for i in range(0, len(nums)):
    if nums[i] != val:
        nums[slow] = nums[fast]
        slow += 1
return slow