二分搜索和归并排序，list index out of range

小城的悠闲

寻找一个随机列表中是否存在相反的数  a= -a
我写了一段代码，先用merge_sort 排序，然后用二分法寻找 -a是否存在。
运行的时候，总是反馈 list index out of range。
但是，单独运行二分搜索的时候，则没有list index out of range。到底怎么了。。。

1. import random as ra
   
2. 
   
3. # 寻找相反数
   
4. def sum_t(l):
   
5.     sum_two = False
   
6.     l = merge_sort(l)
   
7.     for dd in l:
   
8.         if bins(l,-dd):
   
9.            sum_two= True
   
10.            t = dd
    
11.     return sum_two, t
    
12. #产生随机数列
    
13. def ralist(n):
    
14.     a = []
    
15.     for i in range(n):
    
16.         b = ra.randint(-100, 100)
    
17.         if b not in a:
    
18.             a.append(b)
    
19.     return a
    
20. #归并法排序
    
21. def merge_sort(a):
    
22.     last = len(a)
    
23.     if last == 1:
    
24.         return a
    
25.     else:
    
26.         m = last//2
    
27.         left = a[:m]
    
28.         right = a[m:]
    
29.         return mergei(merge_sort(left),merge_sort(right))
    
30.    
    
31. def mergei(left, right):
    
32.     result = []
    
33.     while len(left)>0 and len(right)>0:
    
34.         if left[0] <= right[0]:
    
35.             result.append(left.pop(0))
    
36.         else:
    
37.             result.append(right.pop(0))
    
38.     result = result + left
    
39.     result = result + right
    
40.     return result        
    
41. 
    
42. #递归法二分搜索
    
43. def bins(A,n):
    
44.     last = len(A)
    
45.    
    
46.     found = False
    
47.     m = last//2
    
48.    
    
49.     if n == A[m]:
    
50.         found = True
    
51.     elif m >0 and not found:
    
52.         if n > A[m]:
    
53.             return bins(A[m+1:], n)
    
54.         else:
    
55.             return bins(A[:m],n)
    
56.     return found
    
57. 
    
58. #运行
    
59. k = ralist(40)
    
60. sum_t(k)
    

复制代码

傻眼貓咪

温馨提示：你的代码没有注解，看起来比较费力，最好加些注解，方便别人检查你的代码

suchocolate

bins函数没有考虑到A等于[]的情况，所以报错了。
如果只是练习二分法，没有必要用递归，二分法用循环就行。以下是力扣上的案例：

1.     def search(self, nums: List[int], target: int) -> int:
   
2.         low, high = 0, len(nums) - 1
   
3.         while low <= high:
   
4.             mid = (high - low) // 2 + low
   
5.             num = nums[mid]
   
6.             if num == target:
   
7.                 return mid
   
8.             elif num > target:
   
9.                 high = mid - 1
   
10.             else:
    
11.                 low = mid + 1
    
12.         return 0

复制代码

jackz007

1. #coding:gbk
   
2. 
   
3. '''本程序产生出 40 个值在 -100～100 之间的随机数，然后，利用二分法找出其中 x , -x 同时存在的数据对'''
   
4. 
   
5. import random
   
6. 
   
7. def gen(d , n):
   
8.     k = 0
   
9.     while k < n :
   
10.         x = random . randint(-100 , 100)
    
11.         if not x in d:
    
12.             d . append(x)
    
13.             k += 1
    
14. 
    
15. def find(d , x):
    
16.     a , c , r = 0 , len(d) - 1 , -1
    
17.     while d[a] <= x <= d[c]:
    
18.         b = a + (c - a) // 2
    
19.         if d[b] == x:
    
20.             r = b
    
21.             break
    
22.         else:
    
23.             if d[b] > x:
    
24.                 c = b
    
25.             else:
    
26.                 a = b + 1
    
27.     return r
    
28. 
    
29. e , d = [] , []
    
30. gen(d , 40)
    
31. d . sort()
    
32. for i in range(len(d)):
    
33.     x = d[i]
    
34.     if x and not x in e and not -x in e:
    
35.         k = find(d , -x)
    
36.         if k >= 0:
    
37.             e . append(x)
    
38.             print('found %d and %d' % (x , -x))
    
39. print(*d)

复制代码

小城的悠闲

傻眼貓咪 发表于 2021-10-19 08:23
温馨提示：你的代码没有注解，看起来比较费力，最好加些注解，方便别人检查你的代码

添加了

小城的悠闲

suchocolate 发表于 2021-10-19 10:36
bins函数没有考虑到A等于[]的情况，所以报错了。
如果只是练习二分法，没有必要用递归，二分法用循环就行 ...

还是需要递归二分搜索的。。。问题是，单独运行二分搜索时不报错。执行寻找sum_t函数时报错。

小城的悠闲

jackz007 发表于 2021-10-19 14:41

不可以用sort。不可以用逐个比较。因为逐个比较的时间复杂度时n2

小城的悠闲

suchocolate 发表于 2021-10-19 10:36
bins函数没有考虑到A等于[]的情况，所以报错了。
如果只是练习二分法，没有必要用递归，二分法用循环就行 ...

感谢提醒，我加了个边界，基本解决了
def bins(A,n):
    last = len(A)
           
    found = False
    if last == 0:
        return False
   
    m = last//2
   
    if n == A[m]:
        found = True
    elif m >0 and not found:
        if n > A[m]:
            return bins(A[m+1:], n)
        else:
            return bins(A[:m],n)
    return found