二分法的两种实现(循环、递归及查找次数)

li=[i for i in range(10000000)]
s=23000
def compare(start=0,end=len(li),now=len(li)//2):
if li[start]<s<li[now]:
end = now
now=(now+start)//2
start=start
elif li[now]<s<li[end]:
start=now
now = (now+end) // 2
end=end
elif s==li[start]:
return start
elif s==li[now]:
return now
elif s==li[end]:
return end
return compare(start,end,now)
print(compare())


li=[i for i in range(0,10)]
s=1
def compare(start=0,end=len(li)-1,now=(len(li)-1+0)//2,n=0):
if li[start]<s<li[now]:
end = now
n+=1
print(f'{n}次,{start}{now}{end}')
now=(now+start)//2
start=start
n += 1
print(f'{n}次,{start}{now}{end}')
elif li[now]<s<li[end]:
start=now
n += 1
print(f'{n}次,{start}{now}{end}')
now = (now+end) // 2
end=end
n += 1
print(f'{n}次,{start}{now}{end}')
elif s==li[start]:
n += 1
print(f'{n}次,{start}{now}{end}')
return start,n
elif s==li[now]:
n += 1
print(f'{n}次,{start}{now}{end}')
return now,n
elif s==li[end]:
n += 1
print(f'{n}次,{start}{now}{end}')
return end,n
return compare(start,end,now,n)
print(compare())
li=[i for i in range(100)]
s=23
start=0
end=100
now=50
while 1 :
if li[start]<s<li[now]:
end = now
now=(now+start)//2
start=start
elif li[now]<s<li[end]:
start=now
now = (now+end) // 2
end=end
elif s==li[start]:
m= start
break
elif s==li[now]:
m=now
break
elif s==li[end]:
m= end
break
print(m)
原文地址:https://www.cnblogs.com/diracy/p/13371432.html