704.二分查找
题目简述
一个有序数组中找到目标值，返回其位置
思路
确定左右指针，一个指向最左边，一个指向最右边
1. 闭区间
确定中间值，如果中间值大于目标值，目标值在左边，中间值已经确定是不等于目标值的了，那也就没必要将right变成middle，这时候可以往前一个，取为middle-1。与之对应，left取为middle+1。
class Solution: def search(self, nums: List[int], target: int) -> int: n = len(nums) left =0 right = n-1 # 定义target在左闭右闭区间里面，即[left,right] while(left<=right): # 当left=right，区间[left,right]仍然有效，需要判断 middle=left+(right-left)//2 # 防止溢出，这种形式也能表示取中值 if nums[middle] == target: return middle elif nums[middle]<target: left = middle+1 # 既然middle不是，那就赋值为middle+1 else: right = middle-1 # 既然middle不是，那就赋值middle-1# 没找到target return -1
这里不用单独讨论数组为空的情况，当数组为空的时候，left一开始为0，right一开始为-1，直接不进入循环，直接return -1。
2. 左闭右开
确定中间值，如果中间值大于目标值，目标值在左边，中间值已经确定是不等于目标值的了，那也就没必要将right变成middle，这时候可以往前一个，取为middle-1。与之对应，left取为middle+1。
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left =0
right = n # 定义target在左闭右开区间里面，即[left,right)
while(left<right): # 当left=right，[left,right)里面没有元素，是无效空间，于是使用<
middle=left+(right-left)//2 # 防止溢出，这种形式也能表示取中值
if nums[middle] == target:
return middle
elif nums[middle]<target:
left = middle+1 # 既然middle不是，那就赋值为middle+1
else:
right = middle # target在左区间，在[left,middle)之中
# 没找到target
return -1
需要注意的小细节：
1. 找中间值时，避免超出范围，不建议写左加右除以二，建议使用左边值加区间一半写法。因为int有范围，两个大数相加可能超过范围就变成负数了，第二种也存在这种情况，但是发生概率会小点。
2. 跳出循环时，就意味着没有找到，返回-1
3. 这里的left和right取middle还是middle+1/middle-1，需要注意，根据要判断的区间的开闭性来确定是否加减1。
27.移除元素
题目简述
删掉数组中指定的元素，其他元素可以保留，数组前面的数是准确的即可。
思路
双指针法
1. 两个指针都从左边开始
一个指针用来指向下一个被改变数值的位置，一个指针遍历数组，寻找非指定元素，存入第一个指针指向的位置。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
ptr1=0 # 指向待改变的位置
n=len(nums)
for ptr2 in range(n): # ptr2用来遍历整个数组
if nums[ptr2]!=val:
nums[ptr1]=nums[ptr2]
ptr1+=1
return ptr1
2. 对上面的双指针进行优化处理
两个指针一左一右。如果左指针left指向的元素等于val，将右指针right指向的元素复制到左指针left的位置，然后右指针左移一位。如果赋值过来的元素恰好也等于val，那就继续把右指针right指向的元素的值赋值过来，直到左指针指向的元素的值不等于val为止。
当right取len(nums)，此时循环判断条件为while(left<right)，意味着对下标为[0, len(nums)) 中的元素进行操作，刚好囊括了所有元素。对应如下代码实现：
class Solution: def removeElement(self, nums: List[int], val: int) -> int: left=0 right=len(nums) while(left<right): if nums[left]==val: nums[left]=nums[right-1] right-=1 else: left+=1 return left
当right取len(nums)-1，此时循环判断条件为while(left<=right)，意味着对下标为[0,len(nums)-1]中的元素进行操作，刚好囊括了所有元素。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left=0
right=len(nums)-1
while(left<=right):
if nums[left]==val:
nums[left]=nums[right]
right-=1
else:
left+=1
return left
总结
1. 边界条件要仔细思考，注意开闭性
标签：27,nums,704,middle,int,right,移除,指针,left From： https://www.cnblogs.com/cp1999/p/17219053.html