非递归二分查找算法,Python二分查找算法

　　一、初始递归

　　递归函数：在函数中，函数本身被调用。

　　最大递归深度：998

　　正如你刚才看到的，递归函数如果没有受到外力的阻挡，总是会被执行的。但是，我们之前已经讲过函数调用的问题了。每个函数调用都会产生自己的名称空间。如果一直调用，会导致命名空间占用太多内存。于是python强制将递归级别控制在997(只要997！买不到就吃亏；买不到就被骗了.).

　　用什么可以证明这个“998理论”？这里我们可以做一个实验：

　　国防后勤(北):

　　打印(n)

　　n=1

　　食物

　　O (1)由此我们可以看到，在我们报告错误之前，我们可以看到的最大数量是998。当然，997是python为我们程序的内存优化设置的默认值，我们当然可以通过一些方法修改它：

　　导入系统

　　print(sys . setrecursionlimit(100000))我们可以这样修改递归的最大深度。刚才我们把python允许的递归深度设置为10w。至于实际能达到的深度，就看电脑的性能了。但是我们还是不建议修改这个默认的递归深度，因为如果你用997级的递归来解决问题，要么是用递归不合适，要么是你的代码很烂~ ~ ~

　　看到这里，你可能会觉得递归不是什么好东西，不如while True好用！不过江湖上流传着一句话，人懂循环，神懂递归。所以不要小看递归函数。很多人这么多年都被挡在大神的门槛之外，就是因为他们没能理解递归的真正含义。而且我们后面要学的很多算法都会和递归有关。加油，学了才有资本抛弃！

　　二、递归示例讲解

　　这里有另一个例子来说明递归可以做什么。

　　示例1:

　　现在你问我，亚历克斯老师多大了？我说过我不会告诉你，但是亚历克斯比埃贡大两岁。

　　如果你想知道亚历克斯多大了，还用问埃贡吗？埃贡说，我也不告诉你，我比先生大两岁。

　　你又问了吴sir，吴sir没告诉你。他说他比太白大两岁。

　　你问太白，太白会告诉你他18。

　　这时候你知道了吗？亚历克斯多大了？

　　金鑫182吴sir203egon224

　　valign="middle">alex24你为什么能知道的？

　　首先，你是不是问alex的年龄，结果又找到egon、武sir、太白，你挨个儿问过去，一直到拿到一个确切的答案，然后顺着这条线再找回来，才得到最终alex的年龄。这个过程已经非常接近递归的思想。我们就来具体的我分析一下，这几个人之间的规律。

age(4) = age(3) + 2 
　　age(3) = age(2) + 2
　　age(2) = age(1) + 2
　　age(1) = 40

def age(n):
　　 if n == 1: 
　　 return 40
　　 else: 
　　 return age(n-1)+2print(age(4))

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

　　l.index(66)...

　　我们之所以用index方法可以找到，是因为python帮我们实现了查找方法。如果，index方法不给你用了。。。你还能找到这个66么？

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
　　i = 0for num in l: if num == 66:
　　 print(i)
　　 i+=1

　　但我们现在是怎么找到这个数的呀？是不是循环这个列表，一个一个的找的呀？假如我们这个列表特别长，里面好好几十万个数，那我们找一个数如果运气不好的话是不是要对比十几万次？这样效率太低了，我们得想一个新办法。

　　二分查找算法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

　　如果这样，假如我要找的数比列表中间的数还大，是不是我直接在列表的后半边找就行了？

　　这就是二分查找算法！

　　那么落实到代码上我们应该怎么实现呢？

　　简单版二分法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]def func(l,aim):
　　 mid = (len(l)-1)//2
　　 if l: if aim > l[mid]:
　　 func(l[mid+1:],aim) elif aim < l[mid]:
　　 func(l[:mid],aim) elif aim == l[mid]:
　　 print("bingo",mid) else:
　　 print('找不到')
　　func(l,66)
　　func(l,6)

l1 = [1, 2, 4, 5, 7, 9]
　　def two_search(l,aim,start=0,end=None):
　　 end = len(l)-1 if end is None else end
　　 mid_index = (end - start) // 2 + start 
　　 if end >= start:
　　 if aim > l[mid_index]:
　　 return two_search(l,aim,start=mid_index+1,end=end
　　 elif aim < l[mid_index]:
　　 return two_search(l,aim,start=start,end=mid_index-1) 
　　 elif aim == l[mid_index]:
　　 return mid_index 
　　 else:
　　 return '没有此值'
　　 else:
　　 return '没有此值'
　　print(two_search(l1,9))

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。