如何用 Array#bsearch 与 Range#bsearch 在 Ruby 中执行二分搜索【免费下载链接】rubyThe Ruby Programming Language项目地址: https://gitcode.com/GitHub_Trending/ru/ruby在 Ruby 中对已排序的数据做查找时线性扫描find、index是 O(n) 的。Ruby 官方文档 Binary Searching 描述了三个支持二分搜索的方法Array#bsearch、Array#bsearch_index和Range#bsearch。它们按块block的判定结果在 O(log n) 操作内从self中选出满足条件的元素或元素下标其中 n 是元素个数。前提是你的数据必须已排序——文档明确指出这一点“不会被检查”排序责任在使用方。两种搜索模式先决定块该返回什么这三个方法没有显式的“模式参数”模式由块返回值的类型决定文档将其分为两类Find-minimum找最小模式块必须返回true或false。方法返回块第一次返回true的那个元素。Find-any找任意模式块必须返回一个数值。方法返回某个使块返回零的元素找不到时返回nil。文档同时提醒块不应混用两种模式有时返回true/false、有时返回数值但这同样不会被检查。不传块时bsearch返回一个 Enumerator这一点在 array.c 的方法签名注释中也有对应bsearch - new_enumerator。用 Array#bsearch 做 Find-minimum 查找Find-minimum 模式对块有一个隐含要求不被检查不存在下标i和j0 i j self.size使得块对self[i]返回true而对self[j]返回false。用文档的表述所有返回false的元素必须排在所有返回true的元素之前。文档给出的示例可直接在 Ruby 控制台按原样执行a [0, 4, 7, 10, 12] a.bsearch {|x| x 4 } # 4 a.bsearch {|x| x 6 } # 7 a.bsearch {|x| x -1 } # 0 a.bsearch {|x| x 100 } # nil如何判断自己写的块是否符合这个模式文档给出的办法是把块逐个元素套用到数组上检查结果序列是否“先 false 后 true”a [0, 4, 7, 10, 12] a.map {|x| x 4 } # [false, true, true, true, true] a.map {|x| x 6 } # [false, false, true, true, true] a.map {|x| x -1 } # [true, true, true, true, true] a.map {|x| x 100 } # [false, false, false, false, false] # 下面这种块在该模式下没有意义中间出现 true、两边是 false a.map {|x| x 7 } # [false, false, true, false, false]x 7这类“精确相等”的块不满足单调性不属于 find-minimum 模式要精确查找应使用下面的 find-any 模式。用 Array#bsearch 做 Find-any 精确查找Find-any 模式要求块返回数值并且符号序列必须满足所有正值的元素排在零值元素之前所有正值的元素排在负值元素之前所有零值元素排在负值元素之前。典型写法是用比较目标值与元素a [0, 4, 7, 10, 12] a.bsearch {|element| 7 element } # 7 a.bsearch {|element| -1 element } # nil a.bsearch {|element| 5 element } # nil a.bsearch {|element| 15 element } # nil用同样的 map 手法检查这些块a [0, 4, 7, 10, 12] a.map {|element| 7 element } # [1, 1, 0, -1, -1] a.map {|element| -1 element } # [-1, -1, -1, -1, -1] a.map {|element| 5 element } # [1, 1, -1, -1, -1] a.map {|element| 15 element } # [1, 1, 1, 1, 1] # 方向写反的块负值出现在零值之前在该模式下没有意义 a.map {|element| element 7 } # [-1, -1, 0, 1, 1]注意方向7 element在数组前半段返回正数、后半段返回负数中间恰好是 0符合文档要求的符号排列而element 7的顺序相反文档明确标注这种块“没有意义”。当目标值有重复时find-any 模式返回其中“某个”匹配项而不是固定的一项。文档示例#后为文档给出的可能结果a [0, 100, 100, 100, 200] r (0..4) r.bsearch {|i| 100 - a[i] } # 1, 2 or 3 r.bsearch {|i| 300 - a[i] } # nil r.bsearch {|i| 50 - a[i] } # nil如果只想要下标而不是元素本身用Array#bsearch_index其调用形式在 array.c 的注释中为bsearch_index {|element| ... } - integer or nil。用 Range#bsearch 搜索取值范围Range#bsearch把同样的逻辑用于区间本身返回的是区间内被选中的值。文档给出两类典型用法。在索引空间上做二分查找用区间下标间接访问数组a [0, 4, 7, 10, 12] r (0...a.size) r.bsearch {|i| a[i] 4 } # 1 r.bsearch {|i| a[i] 6 } # 2 r.bsearch {|i| a[i] 8 } # 3 r.bsearch {|i| a[i] 100 } # nil在连续实数区间上求近似解文档用对数函数演示r (0.0...Float::INFINITY) r.bsearch {|x| Math.log(x) 0 } # 1.0range.c 中的实现注释还说明了浮点区间的具体处理浮点数被映射为 64 位整数进行比较且-0.0会映射到与0.0相同的整数值以避免(-1...0.0).bsearch得到-0.0。结果验证与已知限制结果判读块对所有元素都不满足条件如x 100的示例时返回nilfind-any 模式找不到使块返回零的元素时同样返回nil。块的合法性自行验证文档提供map演示序列的方式上文两节都使用了。bsearch本身不校验“所有 false 在 true 之前”或“正、零、负符号排列”块不符合单调性要求时得到的结果不可信。排序前提不被检查self必须已排序方法内部不做检查。块返回值的类型在 array.c 的rb_ary_bsearch_index实现中块返回值若是数值按 find-any 规则与零比较true按满足处理其余假值按不满足处理返回其他类型时会抛出TypeError消息为wrong argument type ... (must be numeric, true, false or nil)。以上规则对Array#bsearch、Array#bsearch_index和Range#bsearch同时适用完整的模式定义与示例见 doc/language/bsearch.rdoc。仓库的基准测试目录中还有针对区间搜索的用例如 benchmark/range_bsearch_fixnum.yml可以作为实际调用写法的参考。【免费下载链接】rubyThe Ruby Programming Language项目地址: https://gitcode.com/GitHub_Trending/ru/ruby创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考