返回lis中给定数字之前的数字

2024-03-28 09:30:42 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在尝试编写一个二进制搜索,它将在有序列表中的给定数字之前生成最大的数字。你知道吗

y = int(input("Enter a number:"))
numblist = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35]

lowerval = numblist[0]
higherval = numblist[9]
number = 0

mid = (higherval + lowerval)//2

for y in numblist:
   number += 1
if mid == y:
   print(number)
   break

if mid < y:
    lowerval = mid
else:
    higherval = mid
    mid = (higherval + lowerval)//2

例如,如果我输入20,返回的数字应该是18。我真的不知道该怎么称呼正确的位置。我对python非常陌生,所以任何帮助都将不胜感激。你知道吗


Tags: innumberforinputif二进制数字int
3条回答

下面的代码片段将按您的要求执行,尽管方式相对笨拙(但更容易理解):

# Ask the user for an input
y = int(input("Enter a number: "))
# List of numbers to be searched
numblist = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35]

# Set the lower bound of the search
lowerval = numblist[0]
# Set the upper bound of the search
higherval = numblist[-1]


# Search Algorithm
while True:
    mid = (lowerval + higherval) // 2
    if mid == y:
        # Here, I am assuming that you will only test against a list with only unique values.
        # It first indexes the value that was found, then subtracts one from it to obtain the value prior to the found value.
        print(numblist[numblist.index(y) - 1])
        # Then it exits the while loop.
        break
    if mid < y:
        lowerval = mid
    if mid > y:
        higherval = mid

希望这有帮助!你知道吗

似乎,根据你的代码,二进制搜索有一个概念上的问题。如果我们先解决这个问题,代码应该更有意义。你知道吗

什么是二进制搜索?

给定一个有序的列表和一个您正在搜索的项目,您将列表减半,然后依次查看每一半。让我们用一个例子来看看这个。给定[1, 2, 3, 4, 5, 6]并搜索5,您将看到列表的两部分[1,2,3][4,5,6]。查看前半部分([1,2,3]),您注意到最大的项是3。假设列表是有序的,那么列表中的所有项都必须小于3。这意味着5(您正在搜索的内容)不可能在较小的列表中。现在来看([4,5,6])。让我们把它分成两个列表[4][5,6],依此类推。你知道吗

如何将二进制搜索应用于我的问题

给定一个数字列表和一个搜索项,您需要返回列表中最大的项目,该项目仍然小于搜索项。你知道吗

将列表分成两等分(尽可能等分,奇数大小的列表总是不均匀的)。看下半部分列表中最小的一项。如果最小的项大于搜索项,那么您就知道您要查找的值在前半个列表中。否则,它就在下半部分列表中。继续把清单分开,直到你得到你需要的东西。你知道吗

代码是什么样子的

def largest_item_less_than_x(x, list_of_vals):
    size = len(list_of_vals)

    if (size == 0):
        return None

    if (size == 1):
        if (list_of_vals[1] < x):
            return list_of_vals[1]
        else:
            return None
    else:
        mid = size // 2
        left_half_list = list_of_vals[0:mid]
        right_half_list = list_of_vals[mid:]

        if (right_half_list[0] < x):
            return largest_item_less_than_x(x, right_half_list)
        else:
            return largest_item_less_than_x(x, left_half_list)

让我们浏览一下代码。如果你给它一个空列表,它将返回无。也就是说,如果没有可供选择的元素,搜索一个项将不会返回任何结果。你知道吗

如果你给它一个单一的列表,它的值大于你要搜索的值,它将返回None,即给定[6]和搜索3,那么你将无法找到你要找的。你知道吗

如果你给它一个列表,它的值比你要搜索的要小,它就会返回这个值。你知道吗

如果给它一个包含多个项目的列表,那么它会将列表分成两半,并递归地搜索每一半。你知道吗

希望这有道理。你知道吗

这段代码应该允许你做你想做的事,尽管我不确定用户是否需要输入列表中的数字。你知道吗

def bin_search(arr,low,high,elem):
    mid = (low + high)//2
    if low <= high:
        # found element or hit end of list
        if mid == 0 or mid == len(arr) -1 or arr[mid] < elem and arr[mid+1] >= elem:
            print(arr[mid])
            return
        if arr[mid] < elem:
            bin_search(arr,mid+1,high,elem)
        else:
            bin_search(arr,low,mid-1,elem)



y = int(input("Enter a number: "))
numblist = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35]

lowerval = numblist[0]
higherval = numblist[-1]

# special cases 

# highest value is smaller
if higherval < y:
    print(higherval)
# no such value is larger
elif lowerval > y:
    print("-1")
else:
    bin_search(numblist,0,len(numblist)-1,y)

相关问题 更多 >