Python实现二分查找算法
- 二分查找也叫折半查找,每次搜索空间减为原来的一半。减少遍历次数来提高性能
- 温馨提示:折半查找只适用于有序序列
def binarySerach(l,n):
high = len(l)-1
low = 0
while low<=high :
midd=(high-low)//2
if l[midd] == n :
return l[midd]
elif l[midd] > n :
high=midd-1
else :
low=midd+1
return -1
l = [1,3,5,7,8,9,10]
flag = binarySerach(l,8)
if flag != -1 :
print(flag)
else :
print('不存在!')
例题
- 有一个已经排好序的放整数的列表(数字从小到大),输入要查找的数据,如果在列表中找到该数据,输出该数据在列表的下标(索引),否则输出“找不到该数据”
nums = [1, 2, 3, 4, 6, 7, 8, 10, 10, 34, 45]
n = int(input('输入你要查找的数:'))
print(nums, f'列表的长度{len(nums)}')
low = 0
high = len(nums) - 1
while low <= high:
middle = (high + low) // 2
if nums[middle] == n:
print(f'出现的下标索引:{nums.index(n)}')
break
elif nums[middle] > n:
high = middle - 1
else:
low = middle + 1
if low > high or high < low:
print('没有找到')
break
def binarySecher(l, n):
list = l
high = len(list) - 1
low = 0
while low <= high:
mid = (low + high) // 2
if list[mid] == n:
return f'存在出现{list[mid]},索引:{mid}'
if list[mid] > n:
high = mid - 1
if list[mid] < n:
low = mid + 1
return '没有找到'
|