看到题目第一反应index函数，原谅早已把数据结构算法抛之脑后也没系统学过
left和right边界指示变量，while循环即可class Solution:
def search(self, nums: List[int], target: int) -> int:
list_len = len(nums)
left = 0
right = list_len - 1
while left <= right:
middle = (left + right) // 2
if target > nums[middle]:
left = middle + 1
elif target < nums[middle]:
right = middle - 1
else:
return middle
return -1
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)
while left < right:
middle = (left + right) // 2
if target > nums[middle]:
left = middle + 1
elif target < nums[middle]:
right = middle
else:
return middle
return -1
该题目类似于# 704，但是返回条件略微复杂
while循环退出时的情况进行精确分析（这里不分析找到元素的情况，因为该情况和# 704相同）while循环的退出条件是固定的，即left==right首先确定left和right如何变化，left由middle+1得到，right则直接等于middle, 首先证明left移动时永远不会大于right, 即middle+1<=right恒成立
证明：
∵
m
i
d
d
l
e
=
⌊
(
l
e
f
t
+
r
i
g
h
t
)
/
2
⌋
∴
m
i
d
d
l
e
+
1
=
⌊
(
l
e
f
t
+
r
i
g
h
t
)
/
2
⌋
+
1
∵
l
e
f
t
移动之前
l
e
f
t
<
r
i
g
h
t
恒成立
∴
l
e
f
t
≤
r
i
g
h
t
−
1
恒成立
∴
(
m
i
d
d
l
e
+
1
)
∗
2
=
⌊
(
l
e
f
t
+
r
i
g
h
t
)
/
2
⌋
∗
2
+
2
≤
⌊
(
r
i
g
h
t
−
1
+
r
i
g
h
t
)
/
2
⌋
∗
2
+
2
≤
(
r
i
g
h
t
−
1
)
∗
2
+
2
≤
2
∗
r
i
g
h
t
∴
m
i
d
d
l
e
+
1
≤
r
i
g
h
t
\begin{aligned} &\because middle = \lfloor(left + right) / 2\rfloor \\ &\therefore middle + 1 = \lfloor(left + right) / 2\rfloor+1\\ &\because left移动之前left\lt{right}恒成立\\ &\therefore{left}\le{right-1}恒成立\\ &\begin{aligned} \therefore (middle + 1)*2 &= \lfloor(left+right)/2\rfloor*2+2 \\ &\le{\lfloor(right-1+right)/2\rfloor*2+2} \\ &\le{(right-1)*2+2} \\ &\le{2*right} \end{aligned}\\ &\therefore middle+1\le{right} \end{aligned}
∵middle=⌊(left+right)/2⌋∴middle+1=⌊(left+right)/2⌋+1∵left移动之前left<right恒成立∴left≤right−1恒成立∴(middle+1)∗2=⌊(left+right)/2⌋∗2+2≤⌊(right−1+right)/2⌋∗2+2≤(right−1)∗2+2≤2∗right∴middle+1≤right
关键在于middle由向下取整获得，其实默想一下向下取整再加1永远不会超出右边界right
还需证right移动时永远不会小于left, 即left<=middle恒成立，显然成立
因此退出while循环时，left==right
left==right，这里取left进一步分析，此时存在两种情况
0<=left<len(nums)，此时小于目标值target<nums[left]返回left即可，大于则返回left+1left==len(nums)，该情况也是容易遗漏的一点，left不断向right靠拢最后等于right，如果right一直等于数组长度（虚拟边界），此时nums[left]不存在，直接返回left即可class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
list_len = len(nums)
left = 0
right = list_len
while left < right:
middle = (left + right) // 2
if nums[middle] < target:
left = middle + 1
elif nums[middle] == target:
return middle
else:
right = middle
if left == len(nums) or target < nums[left]:
return left
else:
return left + 1
left不会超出数组边界right=middle-1会使得存在right<left的情况，导致while循环退出时不一定left==rightclass Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
list_len = len(nums)
left = 0
right = list_len - 1
while left < right:
middle = (left + right) // 2
if nums[middle] < target:
left = middle + 1
elif nums[middle] == target:
return middle
else:
right = middle - 1
if target < nums[left] or left == right and nums[left] == target:
return left
else:
return left + 1
简单描述为删除指定列表中值等于目标值的所有元素，返回新列表的长度，新列表元素顺序可打乱。
该题目需要先对列表元素逐个进行排查，如果该元素等于目标值val，则从该元素往后找到非val的值与该元素进行替换。即：
val值时，for循环或者while循环向后依次遍历直到找到非val值val值和非val值注：如果第二层for循环或者while循环一直遍历到最后一个元素才找到非val值或一直遍历到最后一个元素都没找到val值，则说明整个列表已经遍历完毕（即没有元素再需要被替换），此时可以直接结束程序
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
total_len = 0
for i in range(len(nums)):
if nums[i] != val:
total_len += 1
continue
else:
j = i + 1
while j < len(nums):
if nums[j] != val:
nums[i], nums[j] = nums[j], nums[i]
total_len += 1
break
j += 1
if j >= len(nums) - 1:
return total_len
return total_len
双指针法指的是用一个后指针从列表尾部向前检索，直到找到非val值，以此替换暴力解法中的第二层for循环或者while循环，时间复杂度为O(n)
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left = 0
right = len(nums) - 1
total_len = 0
while left <= right:
if nums[left] != val:
total_len += 1
left += 1
else:
if nums[right] != val:
nums[left], nums[right] = nums[right], nums[left]
total_len += 1
left += 1
right -= 1
return total_len
该方法使用右指针前后探索，左指针每次只移动一步。
优点
O(n)val值都会被移到最前面，所以左指针可以随意覆盖（不用判断是否等于val）class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# 快指针遍历元素
fast = 0
# 慢指针记录位置
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
两种解法都需要考虑到特殊情况以及边界条件，特殊情况为