python计算3j系数_python之路——二分查找算法

楔子

如果有这样一个列表&＃xff0c;让你从这个列表中找到66的位置&＃xff0c;你要怎么做&＃xff1f;

l &＃61; [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]

你说&＃xff0c;so easy&＃xff01;

l.index(66)...

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

l &＃61; [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&＃61;0for num inl:if num &＃61;&＃61; 66:print(i)

i&＃43;&＃61;1

上面这个方法就实现了从一个列表中找到66所在的位置了。

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

二分查找算法

l &＃61; [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]

你观察这个列表&＃xff0c;这是不是一个从小到大排序的有序列表呀&＃xff1f;

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

这就是二分查找算法&＃xff01;

那么落实到代码上我们应该怎么实现呢&＃xff1f;

简单版二分法

l &＃61; [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]deffunc(l,aim):

mid&＃61; (len(l)-1)//2

ifl:if aim >l[mid]:

func(l[mid&＃43;1:],aim)elif aim

func(l[:mid],aim)elif aim &＃61;&＃61;l[mid]:print("bingo",mid)else:print(&＃39;找不到&＃39;)

func(l,66)

func(l,6)

二分法基础版

升级版二分法

def search(num,l,start&＃61;None,end&＃61;None):

start&＃61; start if start else0

end&＃61; end if end is not None else len(l) - 1mid&＃61; (end - start)//2 &＃43;startif start >end:returnNoneelif l[mid] >num :return search(num,l,start,mid-1)elif l[mid]

二分算法终极版