Ruby的bsearch与bsearch_index处理字符串数组时是否存在异常？

Ruby的bsearch和bsearch_index方法在处理整数数组时表现正常，但处理字符串数组时会出现不符合预期的返回结果，以下是测试细节、原因分析及正确用法说明：

测试场景1：使用start_with?的异常结果 #

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 （不符合预期，数组前3个元素均满足条件）
sorted_strings.bsearch_index { |x| x.start_with? 'aaa' }
#=> nil （不符合预期，数组第一个元素就是"aaa"）
sorted_strings.bsearch_index { |x| x.start_with? 'b' }
#=> 3 （符合预期，第一个以"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" （符合预期）

测试场景2：使用组合比较运算符<=>的异常结果 #

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 （不符合预期，数组第一个元素等于"aaa"）
sorted_strings.bsearch_index { |x| x <=> 'b' }
#=> nil
sorted_strings.bsearch_index { |x| x <=> 'bbb' }
#=> nil （不符合预期，数组索引3的元素是"bbb"）
sorted_strings.bsearch_index { |x| x <=> 'bbc' }
#=> 4 （符合预期）

测试场景3：使用>=比较的正常结果 #

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 Bug，而是未遵循二分查找的模式要求 #

bsearch和bsearch_index是针对有序数组的二分查找方法，对块的返回值有严格的模式要求，不符合要求会导致异常结果：

1. 布尔返回值的「查找最小值模式」

当块返回布尔值时，方法要求数组是分区有序的：存在一个索引k，使得所有小于k的元素返回false，大于等于k的元素返回true（即从某个点开始，所有元素都满足条件）。

• 使用x.start_with?('a')时，数组前3个元素返回true，后续返回false，属于「前半满足、后半不满足」的分区，不符合模式要求，因此返回nil。
• 使用x.start_with?('b')时，前3个元素返回false，后续返回true，符合「从不满足到满足」的分区，因此返回第一个满足条件的索引3。

2. 整数返回值的「查找任意匹配模式」

当块返回整数时，方法要求数组严格有序，且块的返回值需反映元素与目标的大小关系：

• 元素小于目标 → 返回负数
• 元素等于目标 → 返回0
• 元素大于目标 → 返回正数
• 例如x <=> 'a'，所有元素的字典序都大于'a'，块始终返回1（正数），没有元素返回0，因此返回nil；而x <=> 'bbc'时，索引4的元素正好匹配，返回0，因此返回正确索引。

3. >=比较正常工作的原因

x >= 'b'这类条件，正好符合「查找最小值模式」的要求：前3个元素返回false，从索引3开始全部返回true，因此能正确找到第一个满足条件的索引。

正确用法示例 #

如果需要查找第一个以'a'开头的元素索引，可直接使用符合模式的条件：

# 找到第一个大于等于'a'的元素索引（即第一个以'a'开头的元素）
sorted_strings.bsearch_index { |x| x >= 'a' }
#=> 0

如果需要查找最后一个以'a'开头的元素索引，可通过反转条件实现：

# 找到第一个不以'a'开头的元素索引，再减1
first_non_a_index = sorted_strings.bsearch_index { |x| !x.start_with?('a') }
last_a_index = first_non_a_index - 1
#=> 2

内容的提问来源于stack exchange，提问作者Mike Slinn