二分搜索和归并排序，list index out of range
本帖最后由 小城的悠闲 于 2021-10-19 17:11 编辑寻找一个随机列表中是否存在相反的数a= -a
我写了一段代码，先用merge_sort 排序，然后用二分法寻找 -a是否存在。
运行的时候，总是反馈 list index out of range。
但是，单独运行二分搜索的时候，则没有list index out of range。到底怎么了。。。{:9_224:} {:9_224:}
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
return mergei(merge_sort(left),merge_sort(right))
def mergei(left, right):
result = []
while len(left)>0 and len(right)>0:
if left <= right:
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:
found = True
elif m >0 and not found:
if n > A:
return bins(A, n)
else:
return bins(A[:m],n)
return found
#运行
k = ralist(40)
sum_t(k)
温馨提示：你的代码没有注解，看起来比较费力，最好加些注解，方便别人检查你的代码 bins函数没有考虑到A等于[]的情况，所以报错了。
如果只是练习二分法，没有必要用递归，二分法用循环就行。以下是力扣上的案例： def search(self, nums: List, target: int) -> int:
low, high = 0, len(nums) - 1
while low <= high:
mid = (high - low) // 2 + low
num = nums
if num == target:
return mid
elif num > target:
high = mid - 1
else:
low = mid + 1
return 0 本帖最后由 jackz007 于 2021-10-19 15:18 编辑
#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 <= x <= d:
b = a + (c - a) // 2
if d == x:
r = b
break
else:
if d > x:
c = b
else:
a = b + 1
return r
e , d = [] , []
gen(d , 40)
d . sort()
for i in range(len(d)):
x = d
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:
found = True
elif m >0 and not found:
if n > A:
return bins(A, n)
else:
return bins(A[:m],n)
return found
页:
[1]