1.在列表中获取中间位置的值
2.将中间值和所需要查找的值做对比, 如果相等则返回中间值的位置
3.如果中间值小于所需要查找的值, 则将查找范围缩小到 left 至 mid-1 (即right 修改为 mid-1)
4.如果中间值大于所需要查找的值, 则将查找范围修改为 mid+1 至 right (即left 修改为 mid+1)
注: 该算法 永远只查找 中间值是否等于查找值, 无法找到第一个出现 或者最后一个出现的位置
import numpy as np
a = list(np.random.randint(low=0,high=10,size=10))
# sort
a.sort()
print(a)
# a = [0, 2, 2, 3, 4, 7, 7, 7, 8, 9]
a = [0, 3, 3, 4, 4, 5, 6, 8, 9, 9]
def search_b(num):
# set left and right
left = 0
right = len(a)-1
while left < right:
# print("left:%d, right:%d"%(left, right))
# set mid
mid = (right +left)//2
# print("mid:%d"%(mid))
# print(a[mid])
if a[mid] == num:
print("The Number:%d is located %d th in list"%(num, mid))
break
elif a[mid] < num:
left = mid+1
# print("mid < num left:%d;right%d"%(left, right))
else:
right =mid-1
# print("mid > num left:%d;right%d"%(left, right))
return -1
print(search_b(3))