一.二分法概述
[一维数组,折半查找]
假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个[变量]front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.
-
开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为a[mid]>x,故应在前半段中查找。
-
令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>a[mid],故确定应在后半段中查找。
-
令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。
如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。
例:在有序的有N个元素的数组中查找用户输进去的数据x。
算法如下:
-
确定查找范围front=0,end=N-1,计算中项mid=(front+end)/2。
-
若a[mid]=x或front>=end,则结束查找;否则,向下继续。
-
若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内,则把mid+1的值赋给front,并重新计算mid,转去执行步骤2;若a[mid]>x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。
二.Python实现二分法
代码:
import math
list1 = [1,2,3,4,5,6,7,8,9,10]
def finddata(d1):
list_index_min = 0
list_index_max = len(list1) - 1
while list_index_min <= list_index_max:
list_index_middle = (list_index_min + list_index_max) / 2
list_index_middle = math.ceil(list_index_middle)
print(list1[list_index_middle])
print("list_index_min :" + str(list_index_min))
print("list_index_max :" + str(list_index_max))
print("list_index_middle :" + str(list_index_middle))
if list1[list_index_middle] < d1:
list_index_min = list_index_middle + 1
elif list1[list_index_middle] > d1:
list_index_max = list_index_middle - 1
else:
print("find data success! " + str(list1[list_index_middle]) + "\n" )
break
def erfenfa(d1):
"""递归实现二分法"""
if __name__ == '__main__':
print("第一次查找:")
finddata(5)
print("第二次查找:")
finddata(4)
print("第三次查找:")
finddata(3)
print("第四次查找:")
finddata(2)
print("第五次查找:")
finddata(1)
测试记录:
C:\Users\Administrator\AppData\Local\Programs\Python\Python36\python.exe E:/additionalCode/utilities/test1.py
第一次查找:
6
list_index_min :0
list_index_max :9
list_index_middle :5
3
list_index_min :0
list_index_max :4
list_index_middle :2
5
list_index_min :3
list_index_max :4
list_index_middle :4
find data success! 5
第二次查找:
6
list_index_min :0
list_index_max :9
list_index_middle :5
3
list_index_min :0
list_index_max :4
list_index_middle :2
5
list_index_min :3
list_index_max :4
list_index_middle :4
4
list_index_min :3
list_index_max :3
list_index_middle :3
find data success! 4
第三次查找:
6
list_index_min :0
list_index_max :9
list_index_middle :5
3
list_index_min :0
list_index_max :4
list_index_middle :2
find data success! 3
第四次查找:
6
list_index_min :0
list_index_max :9
list_index_middle :5
3
list_index_min :0
list_index_max :4
list_index_middle :2
2
list_index_min :0
list_index_max :1
list_index_middle :1
find data success! 2
第五次查找:
6
list_index_min :0
list_index_max :9
list_index_middle :5
3
list_index_min :0
list_index_max :4
list_index_middle :2
2
list_index_min :0
list_index_max :1
list_index_middle :1
1
list_index_min :0
list_index_max :0
list_index_middle :0
find data success! 1
Process finished with exit code 0
网友评论