返回列表中給定數字之前的數字

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