未找到数字时发现二进制搜索错误

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