未找到數字時發現二進制搜索錯誤

Question

我在查看在線wiki時創建了二進制搜索。我有一類Athletes，每個類都有一個名稱和編號。我輸入一個文件文本或csv，並不重要 - 每個運動員的姓名和號碼。我的程序首先對它們進行排序，然後我嘗試添加基於用戶輸入搜索數字的功能，並顯示誰穿着該編號的球衣。所以我最初的帖子是試圖對具有相同編號的人進行二分查找。如果我的名單上有邁克爾喬丹和勒布朗詹姆斯，他們都會穿23號 - 所以當我的搜索過程中只輸出1（以先到者爲準）。我一直在尋找如何讓我的搜索（下面）接受/查找多次出現的數字。但是，經過進一步測試，我發現如果我輸入的數字實際上並不在我的列表中，它會給我錯誤：search: stack level too deep，我不知道這意味着什麼。我認爲我的搜索不能正確處理，如果沒有實例的數字，或者如果數組爲0 所以我在尋找一些幫助，看看如何解決這個工作，如果用戶輸入的數字不是' t在列表中。所以如果有人輸入「1000」 - 沒有人穿過該球衣號碼，並且應該返回錯誤。或者類似的東西，打破，不管。

def search(array, num, start = 0, last = nil) 
    if last == nil 
    last = array.count - 1 
    end 

    mid = (start + last)/2 

    if num < array[mid].number 
    return search(array, num, start, mid - 1) 
    elsif num > array[mid].number 
    return search(array, num, mid + 1, last) 
    else 
    return mid 
    end 
end 

現在我也得到了==: stack level too deep上線，其中if last == nil

Answer 1

這不是做事的方式紅寶石。當你有一個集合，你想，只選擇其中一些基於特定條件的，紅寶石的方法是使用Enumerable#select

你會非常有運動員的一些陣列，像這樣

athletes = [Athlete.new, Athlete.new] 
athletes_with_number_23 = athletes.select { |athlete| athlete.number == 23 } #if you want all 
first_athlete_wearing_23 = athletes.detect { |athlete| athlete.number == 23 } #if you want only the first one 

聲明：這是僞代碼。

Answer 2

我改變了我的搜索功能：

def search(array, key) 
    lo = 0 
    hi = array.length-1 

    while(lo <= hi) 
    mid = lo + ((hi-lo)/2) 

    if array[mid].number == key 
     return mid 
    elsif array[mid].number < key 
     lo = mid + 1 
    else 
     hi = mid - 1 
    end 
    end 

    puts "Value not found in array" 
end 

Answer 3

如果我有ü的權利，你想獲得所有運動員在排序列表中的具體數量。

首先。你的代碼過於程序化，「這不是做事的紅寶石方式。」但我想這對你並不重要。

因此，我建議你找到一個運動員的索引，並從它左右走陣列來收集相同數目的男子。

這裏是我的程序版本。它使用你的功能。

def athletes_with_number(athletes, number) 
    result = [] 
    found_index = search(athletes, number) 
    return result unless found_index 

    # walk left 
    i = found_index 
    while i >= 0 && athletes[i].number == number 
    result << athletes[i] 
    i -= 1 
    end 

    # walk right 
    i = found_index + 1 # athletes[found_index] already added 
    while i < athletes.size && athletes[i].number == number 
    result << athletes[i] 
    i += 1 
    end 
    result 
end 

def search(array, key) 
    lo = 0 
    hi = array.length-1 

    while(lo <= hi) 
    mid = lo + ((hi-lo)/2) 

    if array[mid].number == key 
     return mid 
    elsif array[mid].number < key 
     lo = mid + 1 
    else 
     hi = mid - 1 
    end 
    end 

    nil 
end