Ruby bsearch 和 bsearch_index 错误？

Question

虽然

bsearch

和

bsearch_index

对于整数数组工作得很好，但它们对于字符串数组似乎有问题。

$ irb
irb(main):001> sorted_strings = %w[aaa aab aac bbb bbc bbd ccc ccd cce]
=> ["aaa", "aab", "aac", "bbb", "bbc", "bbd", "ccc", "ccd", "cce"]
irb(main):002> sorted_strings.bsearch_index { |x| x.start_with? 'a' }
=> nil
irb(main):003> sorted_strings.bsearch_index { |x| x.start_with? 'aaa' }
=> nil
irb(main):004> sorted_strings.bsearch_index { |x| x.start_with? 'b' }
=> 3
irb(main):005> sorted_strings.bsearch_index { |x| x.start_with? 'c' }
=> 6
irb(main):006> sorted_strings.bsearch_index { |x| x.start_with? 'cce' }
=> 8
irb(main):007> sorted_strings.bsearch { |x| x.start_with? 'a' }
=> nil
irb(main):008> sorted_strings.bsearch { |x| x.start_with? 'aa' }
=> nil
irb(main):009> sorted_strings.bsearch { |x| x.start_with? 'aaa' }
=> nil
irb(main):010> sorted_strings.bsearch { |x| x.start_with? 'b' }
=> "bbb"

Nil 永远不应该被归还。这是一个错误吗？

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

$ irb
irb(main):001> sorted_strings = %w[aaa aab aac bbb bbc bbd ccc ccd cce]
=> ["aaa", "aab", "aac", "bbb", "bbc", "bbd", "ccc", "ccd", "cce"]
irb(main):002> sorted_strings.bsearch_index { |x| x <=> 'a' }
=> nil
irb(main):003> sorted_strings.bsearch_index { |x| x <=> 'aaa' }
=> nil
irb(main):004> sorted_strings.bsearch_index { |x| x <=> 'b' }
=> nil
irb(main):005> sorted_strings.bsearch_index { |x| x <=> 'bbb' }
=> nil
irb(main):006> sorted_strings.bsearch_index { |x| x <=> 'bbc' }
=> 4

我不明白为什么以下内容有效，因为上面的内容不起作用：

$ irb
irb(main):001> sorted_strings = %w[aaa aab aac bbb bbc bbd ccc ccd cce]
=> ["aaa", "aab", "aac", "bbb", "bbc", "bbd", "ccc", "ccd", "cce"]
irb(main):002> sorted_strings.bsearch_index { |x| x >= 'a' }
=> 0
irb(main):003> sorted_strings.bsearch_index { |x| x >= 'aa' }
=> 0
irb(main):004> sorted_strings.bsearch_index { |x| x >= 'aaa' }
=> 0
irb(main):005> sorted_strings.bsearch_index { |x| x >= 'b' }
=> 3
irb(main):006> sorted_strings.bsearch_index { |x| x >= 'bbc' }
=> 4
irb(main):007> sorted_strings.bsearch_index { |x| x >= 'cc' }
=> 6
irb(main):008> sorted_strings.bsearch_index { |x| x >= 'cce' }
=> 8

这是我使用的Ruby版本：

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

Answer 1

为了使用

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 的二分搜索方法一起使用的映射可能会有所帮助。