主页 / coding / 问题 / 79333097
Accepted
Mike Slinn
Asked: 2025-01-06 20:55:27 +0800 CST

Ruby bsearch 和 bsearch_index 有错误吗？

  • 772

尽管bsearch和bsearch_index对于整数数组来说工作正常，但它们似乎对字符串数组存在问题。

sorted_strings = %w[aaa aab aac bbb bbc bbd ccc ccd cce]
#=> ["aaa", "aab", "aac", "bbb", "bbc", "bbd", "ccc", "ccd", "cce"]
sorted_strings.bsearch_index { |x| x.start_with? 'a' }
#=> nil
sorted_strings.bsearch_index { |x| x.start_with? 'aaa' }
#=> nil
sorted_strings.bsearch_index { |x| x.start_with? 'b' }
#=> 3
sorted_strings.bsearch_index { |x| x.start_with? 'c' }
#=> 6
sorted_strings.bsearch_index { |x| x.start_with? 'cce' }
#=> 8
sorted_strings.bsearch { |x| x.start_with? 'a' }
#=> nil
sorted_strings.bsearch { |x| x.start_with? 'aa' }
#=> nil
sorted_strings.bsearch { |x| x.start_with? 'aaa' }
#=> nil
sorted_strings.bsearch { |x| x.start_with? 'b' }
#=> "bbb"

永远不应该返回 Nil。这是一个错误吗？

与组合比较运算符进行比较时，会返回更疯狂的结果：

sorted_strings = %w[aaa aab aac bbb bbc bbd ccc ccd cce]
#=> ["aaa", "aab", "aac", "bbb", "bbc", "bbd", "ccc", "ccd", "cce"]
sorted_strings.bsearch_index { |x| x <=> 'a' }
#=> nil
sorted_strings.bsearch_index { |x| x <=> 'aaa' }
#=> nil
sorted_strings.bsearch_index { |x| x <=> 'b' }
#=> nil
sorted_strings.bsearch_index { |x| x <=> 'bbb' }
#=> nil
sorted_strings.bsearch_index { |x| x <=> 'bbc' }
#=> 4

鉴于上述方法无效，我不明白为什么下面的方法有效：

sorted_strings = %w[aaa aab aac bbb bbc bbd ccc ccd cce]
#=> ["aaa", "aab", "aac", "bbb", "bbc", "bbd", "ccc", "ccd", "cce"]
sorted_strings.bsearch_index { |x| x >= 'a' }
#=> 0
sorted_strings.bsearch_index { |x| x >= 'aa' }
#=> 0
sorted_strings.bsearch_index { |x| x >= 'aaa' }
#=> 0
sorted_strings.bsearch_index { |x| x >= 'b' }
#=> 3
sorted_strings.bsearch_index { |x| x >= 'bbc' }
#=> 4
sorted_strings.bsearch_index { |x| x >= 'cc' }
#=> 6
sorted_strings.bsearch_index { |x| x >= 'cce' }
#=> 8

这是我使用的 Ruby 版本：

$ ruby -v
ruby 3.2.2 (2023-03-30 revision e51014f9c0) [x86_64-linux]
ruby

1 个回答

  1. Best Answer

    为了使用bsearch/ bsearch_index，元素必须以特定方式排序。根据二分搜索的文档：

    查找最小值模式
    • [...] 所有false评估元素均位于所有true评估元素之前。
    查找任意模式
    • 所有正值元素均位于所有零值元素之前。
    • 所有正评价元素均位于所有负评价元素之前。
    • 所有零值元素均位于所有负值元素之前。

    但是，在您的示例中，映射是相反的，例如：

    sorted_strings.map { |x| x.start_with? 'a' }
#=> [true, true, true, false, false, false, false, false, false]

sorted_strings.map { |x| x <=> 'bbb' }
#=> [-1, -1, -1, 0, 1, 1, 1, 1, 1]

    它可能会帮助找到map可以与 Ruby 的二进制搜索方法一起使用的映射。

    • 4

相关问题