对于给定的整数集合，要想查找某个元素是否存在我们可以使用 index 操作，如下：
nums = [0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 6, 7, 7, 8, 8, 9, 9, 9, 9] print(nums.index(5)) # 输出索引 9 print(nums.index(10)) # 报错
这里我们使用二分法进行查找，直接上代码：
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(num, n):
left = 0
right = len(num)-1
while left <= right:
mid = (left+right) // 2
if nums[mid] == n:
return mid
if nums[left] <= n < nums[mid]:
right = mid -1
else:
left = mid + 1
return -1
for i in range(-3, 13):
print(i, Bisection(nums, i))
输出：
-3 -1 # 找不到返回 -1 -2 -1 -1 -1 0 0 1 1 2 3 3 5 # 找到 返回其索引 4 8 5 -1 6 9 7 10 8 13 9 15 10 -1 11 -1 12 -1
上述我们基于的一个升序序列，假如对 nums 某个位置进行首位置换一下，比如 nums 变成下面的样子。
nums = [4, 6, 7, 7, 8, 8, 9, 9, 9, 9, 0, 1, 1, 2, 3, 3, 3, 4]
此时，需要修改一下判别条件，左一半或者右一半一定有一个升序序列。
nums = [4, 6, 7, 7, 8, 8, 9, 9, 9, 9, 0, 1, 1, 2, 3, 3, 3, 4]
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def Bisection(num, n):
left = 0
right = len(num) - 1
while left <= right:
mid = (left+right) // 2
if num[mid] == n:
return mid
if num[left] <= num[mid]: # 判断左一半是不是升序的
if num[left] <= n < num[mid]: # 如果是升序的话 判断目标是否在 left mid 里面
right = mid - 1 # 在里面的话更新 right
else: # 虽然是升序 但目标不在这里面
left = mid + 1 # 更新 left 直接舍去这部分
else: # 右一半是升序的
if num[mid] < n <= num[right]: # 判断目标是否在 mid right 里面
left = mid + 1 # 在里面更新 left
else: # 目标不在这里面 更新 right
right = mid - 1
return -1
for i in range(-3, 13):
print(i, Bisection(nums, i))
输出：
-3 -1 -2 -1 -1 -1 0 10 1 11 2 13 3 15 4 0 5 -1 6 1 7 3 8 5 9 8 10 -1 11 -1 12 -1
