python基础--二分查找

二分法算法代码(不用递归,春算法)

 1 lst=[1,2,3,4,5,6,7,8,9,10,62,87,95,410,456,567,894,999]
 2 n=894
 3 left = 0
 4 right = len(lst)-1
 5 count=0
 6 while left<=right:
 7     middle = (left+right)//2
 8     if n<lst[middle]:
 9         right=middle-1
10     elif n>lst[middle]:
11         left=middle+1
12     else:
13         print("计算了%d次"%count)
14         print("n的位置在",middle)
15         break
16     count+=1
17 else:
18     print("不存在")

View Code

二分算法递归1

 1 lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 62, 87, 95, 410, 456, 567, 894, 999]
 2 
 3 
 4 def binary_search(left, right, n):
 5     middle = (left + right) // 2
 6     if left > right:
 7         return -1
 8     if n > lst[middle]:
 9         left = middle + 1
10     elif n < lst[middle]:
11         right = middle - 1
12     else:
13         return middle
14     return binary_search(left, right, n)
15 
16 
17 print(binary_search(0, len(lst) - 1, 45))

View Code

二分算法递归2

 1 lst=[1,2,3,4,5,6,7,8,9,10,62,87,95,410,456,567,894,999]
 2 def binary_search(lst,n):
 3     left = 0
 4     right = len(lst)-1
 5     mid = (left+right)//2
 6     if right <=0:
 7         print("不存在")
 8         return -1
 9     if n>lst[mid]:
10         lst = lst[mid+1:]
11     elif n<lst[mid]:
12         lst = lst[:mid]
13     else :
14         print("存在")
15         return -1
16     binary_search(lst,n)
17 binary_search(lst,1000)

View Code