Ruby 2.0.0 数组#bsearch 行为 [英] Ruby 2.0.0 Array#bsearch behavior

问题描述

我注意到从 Ruby 2.0.0 开始，数组类有一个我正在测试的 bsearch 方法，但我没有得到我期望的行为.为什么它为 2 和 5 返回一个值，而为 -1、1 和 4 返回 nil ?

I noticed that as of Ruby 2.0.0 the array class has a bsearch method that I was testing and I'm not getting the behavior I'd expect. Why does it return a value for 2 and 5 but nil for -1, 1, and 4?

arr_in = [-1, 1, 2, 4, 5]

arr_in.bsearch { |x| x == 3 }   #=> nil
arr_in.bsearch { |x| x == -1 }  #=> nil
arr_in.bsearch { |x| x == 1 }   #=> nil
arr_in.bsearch { |x| x == 2 }   #=> 2
arr_in.bsearch { |x| x == 4 }   #=> nil
arr_in.bsearch { |x| x == 5 }   #=> 5

推荐答案

arr_in = [-1, 1,2,4,5]
arr_in.bsearch{ |x| 2 - x }
#=> 2
arr_in.bsearch{ |x| -1 - x }
#=> -1
arr_in.bsearch{ |x| 3 - x }
#=> nil

二分搜索使用块的结果作为提示，应该选择数组的哪一部分(左侧或右侧)用于下一次迭代的搜索.如果块返回 0，它将停止搜索.如果它返回小于 0 它将向左否则它向右:)

Binary search uses block's result as a hint which part of array (left or right side) should be chosen for searching on next iteration. If block returns 0 it will stop searching. If it returns less then 0 it will go left otherwise it goes right :)

更多信息在这里http://www.ruby-doc.org/core-2.1.1/Array.html#method-i-bsearch

UPD

好的，让我们以你的为例

Ok, let's take your example

arr_in = [-1, 1, 2, 4, 5]
arr_in.bsearch { |x| x == 3 }

首先，我们将获取中间元素 (2) 并将其交给块.2 == 3 将返回 false，因此我们移动到数组的右侧.

First we will take middle element (2) and yield it to the block. 2 == 3 will return false, so we move to the right side of the array.

我们取[4, 5]的中间元素是5，5 == 3是false>

We take middle element of [4, 5] which is 5 and 5 == 3 is false

右边没有任何元素，所以我们将返回nil

There is no any elements on the right, so we will return nil

arr_in = [-1, 1, 2, 4, 5]
arr_in.bsearch { |x| x == 2 }

第一个 2 == 2 是 true.我们向左走.

First 2 == 2 is true. We go to the left.

[-1, 1] 的中间元素为 1.1 == 2 为 false.我们向右走.

Middle element of [-1, 1] is 1. 1 == 2 is false. We go to the right.

[-1, 1] 中没有任何元素在 1 的右边，所以我们返回最后一个返回 true 语句的元素，即 2

There is no any elements in [-1, 1] right to the 1, so we return last last element which returned true statement which is 2

PS:不要忘记，数组应该被排序;)

PS: don't forget, that the array should be sorted ;)

这篇关于Ruby 2.0.0 数组#bsearch 行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！