返回列表中给定数字之前的数字

Question

我正在尝试编写一个二进制搜索，它将在有序列表中给定数字之前产生最高数字。

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非常新，所以任何帮助，将不胜感激。

Answer 1

下面的代码片段会做你想要的东西，虽然在一个相对笨拙的（但更容易理解）时尚：

# 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 

希望这有助于！

Answer 2

此代码应该让你做你想问的问题，但我不确定用户是否需要输入列表中的数字。

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) 

Answer 3

您的代码有几个问题。首先，您在for循环语句中覆盖输入变量y。其次，代码没有正确缩进for循环（可能只是在您的文章中的错误？）。

一些小贴士，帮二进制搜索会：

1. 尝试在列表numblist的中间开始。检查数字是否相等，大于或小于并相应地继续。
2. 使用中间索引而不是在最高值和最低值之间找到中间值。通过这种方式，您实际上将每次都将列表分成两半。
3. 你可能也想考虑while循环而不是for循环。只是一个建议。
4. 假设列表将总是按照您的示例排序，是否安全？如果不是，您可能需要添加一个排序列表的步骤。

这是一段代码，概述了我的建议，似乎工作。可能不是最终答案，但应该有所帮助。

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

found = False 
while not found: 
    print numblist 
    mid = len(numblist)/2 # integer div in python 2 
    if (y == numblist[mid]): 
     found = True 
     x = numblist[mid - 1] 
    elif len(numblist) == 1: 
     found = True 
     x = numblist[0] 
    elif y < numblist[mid]: 
     # search in the lower half 
     numblist = numblist[0:mid] 
    else: 
     # Search in the upper half 
     numblist = numblist[mid:] 

print x 

Answer 4

有一个问题，你的名单真的是升序吗？无论我认为你能做到这一点，

y = int(input("Enter a number:")) 
numblist = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35] 
tempNum = 0 
index = 0 
tempIndex = 0 
for nums in numblist: 
    tempIndex++ 
    if nums != y: 
     if nums > tempNum: 
     tempNum = nums 
     index = tempIndex 
    else: 
     break 
print(tempNum) 
print(numblist[index]) 

所以这循环你的numblist的每个索引。然后它会询问当前发生的事件是否与您输入的数量相同。如果是，则退出循环，如果没有，则比较前一次和当前次数的量。找到你在列表中输入的号码后，它将退出循环。在上一条语句中，您可以打印包含发生前最高数字的tempNum，也可以打印列表中索引最大数字的numblist。希望你能理解我的英语。

Answer 5

看起来，鉴于您的代码，二进制搜索存在概念性问题。如果我们首先解决这个问题，代码应该更有意义。

什么是二分查找？

给出一个有序的列表和一个你正在搜索的项目，你将这个列表减半，然后依次查看每一半。我们来看一个例子。鉴于[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。也就是说，如果没有可供选择的元素，则搜索项目不会返回任何内容。

如果您给它一个值大于您要搜索的值的单个列表，它将返回None，即给出[6]并搜索3，那么您将无法找到您要查找的内容。

如果您给它一个值小于您要搜索的值的单个列表，它会返回该值。

如果您给它一个以上的项目列表，然后它将列表分成两半，并递归搜索每一半。

希望有道理。

Answer 6

这里是一个递归算法二进制搜索发现是x在arr小于元素的索引：

def binary_search_lessthan(x, arr, offset=0): 
    arr = sorted(arr) 
    ix = len(arr)//2 
    if x==arr[ix]: 
     return ix+offset-1 
    elif x<arr[ix]: 
     if len(arr)==1: 
      return offset-1 
     return binary_search_previous(x, arr[:ix], offset) 
    elif x>arr[ix]: 
     if len(arr)==1: 
      return offset 
     return binary_search_previous(x, arr[ix:], offset+ix) 

注意这一点，如果该值小于第一返回-1值在列表中

>>>a = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35] 
>>>binary_search_lessthan(19, a) 
4 
>>>a[binary_search_lessthan(29, a)] 
28 
>>>a[binary_search_lessthan(9, a)] 
8 
>>>a[binary_search_lessthan(8, a)] 
4