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

小城的悠闲

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

import random as ra

# 寻找相反数
def sum_t(l):
    sum_two = False
    l = merge_sort(l)
    for dd in l:
        if bins(l,-dd):
           sum_two= True
           t = dd
    return sum_two, t
#产生随机数列
def ralist(n):
    a = []
    for i in range(n):
        b = ra.randint(-100, 100)
        if b not in a:
            a.append(b)
    return a
#归并法排序
def merge_sort(a):
    last = len(a)
    if last == 1:
        return a
    else:
        m = last//2
        left = a[:m]
        right = a[m:]
        return mergei(merge_sort(left),merge_sort(right))
    
def mergei(left, right):
    result = []
    while len(left)>0 and len(right)>0:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result = result + left
    result = result + right
    return result        

#递归法二分搜索
def bins(A,n):
    last = len(A)
    
    found = 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

#运行
k = ralist(40)
sum_t(k)

傻眼貓咪

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

suchocolate

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

    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = (high - low) // 2 + low
            num = nums[mid]
            if num == target:
                return mid
            elif num > target:
                high = mid - 1
            else:
                low = mid + 1
        return 0

jackz007

#coding:gbk

'''本程序产生出 40 个值在 -100～100 之间的随机数，然后，利用二分法找出其中 x , -x 同时存在的数据对'''

import random

def gen(d , n):
    k = 0
    while k < n :
        x = random . randint(-100 , 100)
        if not x in d:
            d . append(x)
            k += 1

def find(d , x):
    a , c , r = 0 , len(d) - 1 , -1
    while d[a] <= x <= d[c]:
        b = a + (c - a) // 2
        if d[b] == x:
            r = b
            break
        else:
            if d[b] > x:
                c = b
            else:
                a = b + 1
    return r

e , d = [] , []
gen(d , 40)
d . sort()
for i in range(len(d)):
    x = d[i]
    if x and not x in e and not -x in e:
        k = find(d , -x)
        if k >= 0:
            e . append(x)
            print('found %d and %d' % (x , -x))
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