Python实例篇1-python实现二分法

待我称王封你为后i 2022-10-13 14:58 90阅读 0赞

# 一.二分法概述 #

\[一维[数组][Link 1]，折半查找\]

假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个\[变量\]front，mid，end分别指向数据的[上界][Link 2]，中间和下界，mid=（front+end）/2.

1.  开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为a\[mid\]>x，故应在前半段中查找。
2.  令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>a\[mid\]，故确定应在后半段中查找。
3.  令新的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。

算法如下：

1.  确定查找范围front=0，end=N-1，计算中项mid=（front+end）/2。
2.  若a\[mid\]=x或front>=end,则结束查找；否则，向下继续。
3.  若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

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097
[Link 2]: https://baike.baidu.com/item/%E4%B8%8A%E7%95%8C/839017