数据结构二分法python实现

二分法 找到数据\未找到数据，都需要加以判断，以下为python实现：

下面这个以递归实现，不是最简练的方法，但对判断找到和未找到数据，都做了判断实现。

#排序后，二分法排查，找不到key

def func(a,key):
    min = 0
    print("min=", min)
    max = len(a) - 1
    print("max=", max)
    if a!=[]:
        center =int (min + max) // 2
        print("center=", center)
        if a[center]>key:
            max=center-1
            a=a[:max]
            return func(a,key)
        if a[center]<key:
            min=center+1
            a=a[min:]
            return func(a,key)
        if a[center]==key:
            return print("找到key")

    else:return print("不存在")

a=[1,2,3,5,100]
print(a)
func(a,6)

运行结果：

[1, 2, 3, 5, 100]
min= 0
max= 4
center= 2
min= 0
max= 1
center= 0
min= 0
max= 0
center= 0
min= 0
max= -1
不存在

 

以下为逐步推到思路，是while方法，和递归逐渐推导的过程，仅作思路参考

# dichotomy 二分法
#找出数组中等于100的数值

#逐一排查
a=[1,7.9,13,3,6,100,111,5]
#a.sort()
print(a)
for i in range(len(a)):
    print(i + 1)
    print(a[i])
    if a[i]==100:
        print(i,"位置是100")
        break
    else:print("不是100")
print('_'*50)
#排序后，逐一排查
a=[1,7.9,13,3,6,100,111,5]
a.sort()
print(a)
for i in range(len(a)):
    print(i + 1)
    print(a[i])
    if a[i]==100:
        break
    else:print("不是100")



print('_'*50)
#排序后，二分法排查，找到key100
a=[1,7.9,13,3,6,100,111,5]
a.sort()
print(a)
key=100
min=0
print("min=",min)
max=len(a)-1
print("max=",max)

while True:
    center = (min + max) // 2
    print("center=", center)
    if a[center]>key:
        max=center-1
    if a[center]<key:
        min=center+1
    if a[center]==key:
        print("找到100")
        break
print('_'*50)

#排序后，二分法排查，找不到key100
a=[1,7.9,13,3,6,101,111,5]
a.sort()
print(a)
key=100
min=0
print("min=",min)
max=len(a)-1
print("max=",max)

while min<=max:
    center = (min + max) // 2
    print("center=", center)

    if a[center]>key:
        max=center-1
    if a[center]<key:
        min=center+1
    if a[center]==key:
        print("找到100")
        break
else:
    print("不存在")
print('_'*50)

#排序后，二分法排查，找到key

def func(a,key):
    min = 0
    print("min=", min)
    max = len(a) - 1
    print("max=", max)
    center =int (min + max) // 2
    print("center=", center)
    if a[center]>key:
        max=center-1
        a=a[:max]
        return func(a,key)
    if a[center]<key:
        min=center+1
        a=a[min:]
        return func(a,key)
    if a[center]==key:
        print("找到key")

a=[1,2,3,5,100]
print(a)
func(a,5)
print('_'*50)

本文地址：https://blog.csdn.net/linjing0504/article/details/107081838