递归二分查找法——求助

inver11

问题如下：
输入一个列表和数字
判断数字在列表当中的排序并输出排序位置。（数字不添加到列表中）
例子如下：
有一个列表 [4,6,7,3,89,33,45,13,34,54]
给列表排序 [3, 4, 6, 7, 13, 33, 34, 45, 54, 89]   
排序后再给一个数字40   判断40在列表中的位置
按照排序大小 如33<40<45  则40在列表中的位置应该为list[7
要求使用递归二分查找

我的分析流程如下
列表排序
如果数字在列表里 输出在列表中的位置
如果不在：
        如果列表长度等于2：   #如果只剩最后两个数的时候，分别判断即可 并且跳出循环
                如果num>x[0]:     输出此时x[1]  在原列表X中的角标
                 如果num<x[0]:     输出此时x[0]  在原列表X中的角标
                     return 角标
        查找中间的数字num对比大小
        如果大于：
                查找【num：】中间的数字对比大小        调用函数递归
        如果小于：
                查找【：num】中间的数字对比大小        调动函数递归



函数如下：

1. list1 = [4,6,7,3,89,33,45,13,34,54]
   
2. list1.sort()
   
3. def digui(x,y,s=0,i=0):
   
4.     global list1
   
5.     if y in list1:
   
6.         s = list1.index(y)
   
7.         return s
   
8.     else:
   
9.         if len(x)==2 :
   
10.             if y>x[0]:
    
11.                 i = x[1]
    
12.                 s = list1.index(i)
    
13.                 return s
    
14.             elif y<x[0]:
    
15.                 i = x[0]
    
16.                 s = list1.index(i)
    
17.                 return s
    
18.         mid = len(x)//2
    
19.         if y>x[mid]:
    
20.             return digui(x[mid:],y)
    
21.         elif y<x[mid]:
    
22.             return digui(x[:mid],y)
    
23. 
    
24. print(digui(list1,50))

复制代码

以下是报错信息

1. Traceback (most recent call last):
   
2.   File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 24, in <module>
   
3.     print(digui(list1,50))
   
4.   File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui
   
5.     return digui(x[mid:],y)
   
6.   File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui
   
7.     return digui(x[mid:],y)
   
8.   File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 22, in digui
   
9.     return digui(x[:mid],y)
   
10.   File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui
    
11.     return digui(x[mid:],y)
    
12.   File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui
    
13.     return digui(x[mid:],y)
    
14.   File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui
    
15.     return digui(x[mid:],y)
    
16.   [Previous line repeated 987 more times]
    
17.   File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 5, in digui
    
18.     if y in list1:
    
19. RecursionError: maximum recursion depth exceeded in comparison

复制代码

如果把要查找的数字换成是40   则输出6
实际上，按列表排序40  应该是排在[7]才对 输出也是错的




求大佬指点迷津


<div class="blockcode"><blockquote></blockquote></div><br />

zltzlt

1. <div>Traceback (most recent call last):</div><div>  File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 24, in <module></div><div>    print(digui(list1,50))</div><div>  File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui</div><div>    return digui(x[mid:],y)</div><div>  File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui</div><div>    return digui(x[mid:],y)</div><div>  File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 22, in digui</div><div>    return digui(x[:mid],y)</div><div>  File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui</div><div>    return digui(x[mid:],y)</div><div>  File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui</div><div>    return digui(x[mid:],y)</div><div>  File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 20, in digui</div><div>    return digui(x[mid:],y)</div><div>  [Previous line repeated 987 more times]</div><div>  File "C:/Users/Administrator.USER-20181219NC/Desktop/digui.py", line 5, in digui</div><div>    if y in list1:</div><div>RecursionError: maximum recursion depth exceeded in comparison</div>

复制代码

inver11

zltzlt 发表于 2019-8-22 15:36

大佬重新看一下

zltzlt

没报错呀？

inver11

zltzlt 发表于 2019-8-22 15:42
没报错呀？

RecursionError: maximum recursion depth exceeded in comparison

zltzlt

inver11 发表于 2019-8-22 15:44
RecursionError: maximum recursion depth exceeded in comparison

我运行没报错

inver11

zltzlt 发表于 2019-8-22 15:42
没报错呀？

RecursionError: maximum recursion depth exceeded in comparison
python默认的递归深度是很有限的（默认是1000），因此当递归深度超过999的样子，就会引发这样的一个异常。
可是我这个函数，应该只是调用几次就结束了才对啊。。。

zltzlt

inver11 发表于 2019-8-22 15:45
RecursionError: maximum recursion depth exceeded in comparison
python默认的递归深度是很有限的（默 ...

不知道，反正我运行没报错

inver11

zltzlt 发表于 2019-8-22 15:44
我运行没报错

你的结果显示是什么  

zltzlt

6

inver11

zltzlt 发表于 2019-8-22 15:46
6

你把最下面的40改成50试试 就报错了
而且实际上  如果把40放进列表里 40所在的下标也应该是[7]  不是6

zltzlt

1. list1 = [4,6,7,3,89,33,45,13,34,54]
   
2. list1.sort()
   
3. def digui(x,y,s=0,i=0):
   
4.     global list1
   
5.     if y in list1:
   
6.         s = list1.index(y)
   
7.         return s
   
8.     else:
   
9.         if len(x)==2 :
   
10.             if y>x[0]:
    
11.                 i = x[1]
    
12.                 s = list1.index(i)
    
13.                 return s
    
14.             elif y<x[0]:
    
15.                 i = x[0]
    
16.                 s = list1.index(i)
    
17.                 return s
    
18.         mid = round(len(x)/2)
    
19.         if y>x[mid]:
    
20.             return digui(x[mid:],y)
    
21.         elif y<x[mid]:
    
22.             return digui(x[:mid],y)
    
23. 
    
24. print(digui(list1,40))

复制代码

inver11

zltzlt 发表于 2019-8-22 15:53

还是不行呢  输入40   得到结果还是6  不是7
输入50  输出8  是对
但是输入30  又出现递归超出范围的错误。。

zltzlt

inver11 发表于 2019-8-22 16:24
还是不行呢  输入40   得到结果还是6  不是7
输入50  输出8  是对
但是输入30  又出现递归超出范围的错 ...

1. list1 = [4,6,7,3,89,33,45,13,34,54]
   
2. list1.sort()
   
3. def digui(x,y,s=0,i=0):
   
4.     global list1
   
5.     if y in list1:
   
6.         s = list1.index(y)
   
7.         return s
   
8.     else:
   
9.         if len(x)==2 :
   
10.             if y>x[0]:
    
11.                 i = x[1]
    
12.                 s = list1.index(i)
    
13.                 return s
    
14.             elif y<x[0]:
    
15.                 i = x[0]
    
16.                 s = list1.index(i)
    
17.                 return s
    
18.         mid = round(len(x)/2)
    
19.         if not mid:
    
20.             return list1[mid]
    
21.         if y>x[mid]:
    
22.             return digui(x[mid:],y)
    
23.         elif y<x[mid]:
    
24.             return digui(x[:mid],y)

复制代码

inver11

zltzlt 发表于 2019-8-22 16:28

还是不对呢   你输入20，40 30 分别测试一下  得到的结果都是错的

zltzlt

inver11 发表于 2019-8-22 16:38
还是不对呢   你输入20，40 30 分别测试一下  得到的结果都是错的

你这个程序要实现什么功能

inver11

zltzlt 发表于 2019-8-22 16:40
你这个程序要实现什么功能

我加了一个对比位置   正确的位置信息和用函数得到的位置信息对比

1. list1 = [4,6,7,3,89,33,45,13,34,54]
   
2. list1.sort()
   
3. def digui(x,y,s=0):
   
4.     global list1
   
5.     if y in list1:
   
6.         s = list1.index(y)
   
7.         return s
   
8.     else:
   
9.         if len(x)==2 :
   
10.             if y>x[0]:
    
11.                 s = list1.index(x[1])
    
12.                 return s
    
13.             elif y<x[0]:
    
14.                 s = list1.index(x[0])
    
15.                 return s
    
16.         mid = round(len(x)/2)
    
17.         if not mid:
    
18.             return list1[mid]
    
19.         if y>x[mid]:
    
20.             return digui(x[mid:],y)
    
21.         elif y<x[mid]:
    
22.             return digui(x[:mid],y)
    
23. print("这是排序后的列表",end = "")
    
24. print(list1)
    
25. print("'%d'这是数字在列表中应该出现的位置"%digui(list1,40))
    
26. list1.append(40)
    
27. list1.sort()
    
28. print("'%d'这是正确应该出现的位置"%list1.index(40))
    

复制代码

inver11

zltzlt 发表于 2019-8-22 16:40
你这个程序要实现什么功能

输入一个列表和数字
判断数字在列表当中的排序并输出排序位置。
要求使用递归二分查找
这个是我要实现的功能

inver11

再来顶一顶

inver11

有大佬指导一下问题错在哪里吗