基础概念
算法的单调性：问题的规模随着算法的推进不断缩减 （如704中开始的查找区间是[lo,hi),随着循环的进行，问题规模确实在不断的缩小）
算法的不变性：在初始状态下自然满足，当问题的有效规模缩减为0时，不变性应该随即等于正确性。（如704中开始的查找区间是[lo,hi),最终要么直接命中，要么缩减为0后未命中）
数组
连续内存空间，查找o(1),增删O(n) 由于需要移动后面的元素。
任务
704 二分查找
题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
思路：
由于数组有序，遂采用二分查找而非顺序查找，使用界桩lo和hi表示查找区间，mi的值为lo和hi的中间，用来缩减这个区间的大小。如果查找的值小于arr[mi]，则缩减为左半区间，否则缩减为右半区间，直到在搜索过程中命中target,若直到循环结束也没有命中（缩减到空集），说明没有找到，则返回-1。注意这里的界桩表示的是左闭右开，更符合个人的思路，最右侧表示实际元素的后一个元素，与c++迭代器中的end类似，符合 != 语义，表示空集时也更符合直觉 [x,x)。核心就是当前待查找的范围
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo = 0
hi = len(nums)
while lo<hi:
mi = lo + (hi - lo)//2
if target < nums[mi]:
hi = mi
elif target > nums[mi]:
lo = mi + 1
else:
return mi
return -1
如果采取闭区间语义，则实际很类似，有一些循环条件和查找范围中细小的改变，只要保证每处语义符合要求即可。但是个人还是推荐左闭右开的语义去编程
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo = 0
hi = len(nums) - 1
while lo<=hi:
mi = lo + (hi - lo)//2
if target < nums[mi]:
hi = mi -1
elif target > nums[mi]:
lo = mi + 1
else:
return mi
return -1
语言tips 注意python3中的floor除法与之前版本的区别
27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
思路：
1.暴力解法 使用双层循环，外层循环遍历每一个元素，当遍历到符合移除条件的元素时，用后面的值覆盖前面的值，覆盖完成后，数组的size减1，注意i也减1指向新的元素。时间复杂度为O(n^2)
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
size = len(nums)
i = 0
while i < size:
if nums[i] == val:
for j in range(i+1,size):
nums[j-1] = nums[j]
size-=1
i-=1 # 这里的语句也可以改为continue，表示继续检查当前位置
i+=1
return size
2.双指针法： slow指针表示当前归入最终数组中的元素的末尾哨兵（右开），fast指针用来遍历数组，符合条件的就加入到slow所表示的范围中，时间复杂度优化为o(n)
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
size = len(nums)
slow = 0
fast = 0
while fast != size:
if nums[fast] != val:
nums[slow] = nums[fast]
slow+=1
fast+=1
return slow
重要！！！ 语言tips python中的for循环和C++ C#等中的不同！在Python中，for循环中的循环变量i在每次迭代开始时都会被重新赋值为下一个值，而不会保留上次循环中的修改。因此遇到需要在循环中修改循环变量的情况需要用while循环处理
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
思路：
找到插入位置，即将数组分为 [0,lo)中的元素均小于target，而[hi,size)中的元素都大于等于e，即算法的不变性是 左边是<target的区间 ，中间是未知待拓展区间，右边是>=target的区间,初始是左右两边的区间均为空，整个区间都是未知区间；最终，随着算法的迭代，区间变为前面描述的 < 和 e<= 。即lo和hi最终相等等于右边区间的开始第一个即不小于target的第一个元素的索引。核心是将区间划分为 < target 和target <= 的两端 [0,lo) [hi,size)
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
lo = 0
hi = len(nums)
while(lo<hi):
mi = lo+ (hi-lo)//2
if target <= nums[mi]:
hi = mi
else: lo = mi+1
return lo
注意虽然看起来和704的代码很相似，只有边界条件上细微的差别，但实际上的思路是完全不一样的。对于查找失败只用返回-1的情况来说，核心思路是缩小查找的范围，直到最终找到或者为空集。而对于本例来说，核心思路是将原本未知的区间划分成由target分界的两端，最终因为算法的不变性和单调性，一步步迭代，找到分界点。
34. 在排序数组中查找元素的第一个和最后一个位置
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
思路
思路与上面的35相同，35是将区间分为左边都< 右边都>=target，因此如果数组中存在target，则右边第一个就是=target的第一个值。另外，我们将区间分为左边都<= 右边都＞target,因此，如果存在target，左边的最后一个就是数组中最后一个等于target的数。此外，需要处理一些特殊的边界情况，判断实际是否存在等。这里用了两个while循环去找到最前面和最后面的target的索引。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums: return [-1,-1]
lo = 0
hi = len(nums)
while(lo<hi):
mi = lo + (hi - lo)//2
if target <= nums[mi]:
hi = mi
else:
lo = mi + 1
minLargeIndex = lo
if minLargeIndex >= len(nums): return [-1,-1]
if nums[minLargeIndex] != target: return [-1,-1]
lo = 0
hi = len(nums)
while(lo<hi):
mi = lo + (hi - lo)//2
if target < nums[mi]:
hi = mi
else:
lo = mi + 1
maxLessIndex = lo - 1
return [minLargeIndex,maxLessIndex]