给定升序的整数列表：
nums = [0, 1, 1, 2, 3, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9, 9, 9] # 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
但是，上面的 nums 里有的元素出现不止一次，我们需要找出目标第一次出现的索引或者最后一次出现的索引，（参考上一篇）有：
第一次出现的索引：
nums = [0, 1, 1, 2, 3, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9, 9, 9]
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def Bisection_left(num, n):
left = 0
right = len(num)-1
while left <= right:
mid = (left+right) // 2
if n <= nums[mid]:
right = mid -1
else:
left = mid + 1
return left
for i in list(set(nums)):
print(i, Bisection_left(nums, i))
0 0 1 1 2 3 3 4 4 7 6 9 7 10 8 12 9 14
# 对于不在 nums 的元素可以用下面的命令判断
for i in [-1, 5, 10]:
index = Bisection_left(nums, i)
if nums[index] != i or index > len(nums):
print(i, -1)
# -1 -1
# 5 -1
# 10 -1
最后一次出现的索引：
nums = [0, 1, 1, 2, 3, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9, 9, 9]
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def Bisection_right(num, n):
left = 0
right = len(num)-1
while left <= right:
mid = (left+right) // 2
if n >= nums[mid]:
left = mid + 1
else:
right = mid -1
return right
for i in list(set(nums)):
print(i, Bisection_right(nums, i))
0 0 1 2 2 3 3 6 4 8 6 9 7 11 8 13 9 17
# 对于不在 nums 的元素可以用下面的命令判断
for i in [-1, 5, 10]:
index = Bisection_right(nums, i)
if nums[index] != i or index < 0:
print(i, -1)
# -1 -1
# 5 -1
# 10 -1
在这里我们是否问道：能否统计目标在列表中出现的首次和末次的索引，当然可以。
第一种方法：即统计出目标第一次出现的索引 和 最后一次出现的索引
nums = [0, 1, 1, 2, 3, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9, 9, 9]
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def Bisection_left(num, n):
left = 0
right = len(num)-1
while left <= right:
mid = (left+right) // 2
if n <= nums[mid]:
right = mid -1
else:
left = mid + 1
return left
def Bisection_right(num, n):
left = 0
right = len(num)-1
while left <= right:
mid = (left+right) // 2
if n >= nums[mid]:
left = mid + 1
else:
right = mid -1
return right
for i in list(set(nums)):
left = Bisection_left(nums, i)
right = Bisection_right(nums, i)
print(i, [left, right])
0 [0, 0] 1 [1, 2] 2 [3, 3] 3 [4, 6] 4 [7, 8] 6 [9, 9] 7 [10, 11] 8 [12, 13] 9 [14, 17]
第二种方法：即统计出目标第一次出现的索引 和 目标+1 第一次出现的索引
nums = [0, 1, 1, 2, 3, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9, 9, 9]
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def Bisection_left(num, n):
left = 0
right = len(num)-1
while left <= right:
mid = (left+right) // 2
if n <= nums[mid]:
right = mid -1
else:
left = mid + 1
return left
for i in list(set(nums)):
start = Bisection_left(nums, i)
end = Bisection_left(nums, i+1) - 1 # 这里不论 i+1 是否在nums里面，如果不在的话也就是下一个元素的第一个索引
print(i, [start, end]) # 最后一个元素的 i+1 会超出边界 在这里就是 10 的索引是18
0 [0, 0] 1 [1, 2] 2 [3, 3] 3 [4, 6] 4 [7, 8] 6 [9, 9] 7 [10, 11] 8 [12, 13] 9 [14, 17]
def Bisection_right(num, n):
left = 0
right = len(num)-1
while left <= right:
mid = (left+right) // 2
if n >= nums[mid]:
left = mid + 1
else:
right = mid -1
return right
for i in list(set(nums)):
left = Bisection_right(nums, i-1) + 1 # 这里不论 i-1 是否在nums里面，如果不在的话也就是上一个元素的最后一个索引
right = Bisection_right(nums, i) # 第一个元素的 i-1 会超出边界 在这里就是 -1 的索引是-1
print(i, [left, right])
0 [0, 0] 1 [1, 2] 2 [3, 3] 3 [4, 6] 4 [7, 8] 6 [9, 9] 7 [10, 11] 8 [12, 13] 9 [14, 17]
第三种方法：在给出一个双指针的方法
nums = [0, 1, 1, 2, 3, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9, 9, 9]
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def Pointe(num, n):
left = 0
right = len(num)-1
while left <= right:
if num[left] == n:
left = left
else:
left += 1
if num[right] == n:
right = right
else:
right -= 1
if num[left] == num[right]:
break
return [left, right]
for i in list(set(nums)):
print(i, Pointe(nums, i))
0 [0, 0] 1 [1, 2] 2 [3, 3] 3 [4, 6] 4 [7, 8] 6 [9, 9] 7 [10, 11] 8 [12, 13] 9 [14, 17]
