Bug #9782

Array#bsearch skip first match while using block with complex condition

Added by Valentin Syrovatskiy about 1 year ago. Updated about 1 year ago.

[ruby-core:62207]
Status:Rejected
Priority:Normal
Assignee:-
ruby -v:ruby 2.1.1p76 (2014-02-24 revision 45161) [x86_64-linux] Backport:2.0.0: UNKNOWN, 2.1: UNKNOWN

Description

Description: Array#bsearch cannot find first match when using block with condition by hash key.

Example:
$ irb
2.1.1 :001 > [{a:1, b:2}, {a:3, b:4}].bsearch{|x| x[:a] == 1}
=> nil
(WRONG, expected {a:1, b:2})
2.1.1 :002 > [{a:3, b:4}, {a:1, b:2}].bsearch{|x| x[:a] == 1}
=> {:a=>1, :b=>2}
(Correct, successfully find same item if it in second position)
2.1.1 :003 > [{a:3, b:4}, {a:1, b:2}].bsearch{|x| x[:a] == 3}
=> nil
(WRONG, expected {a:3, b:4})
2.1.1 :004 > [{a:3, b:4}, {a:1, b:2}].bsearch{|x| x[:b] == 4}
=> nil
(WRONG, expected {a:3, b:4})
2.1.1 :005 > [{a:3, b:4}, {a:1, b:2}, {a:3, b:5}].bsearch{|x| x[:a] == 3}
=> {:a=>3, :b=>5}
(WRONG, expected {a:3, b:4})

Environment:
$ rvm info
ruby-2.1.1:
system:
uname: "Linux magic 3.14.2-031402-generic #201404262053 SMP Sun Apr 27 00:54:28 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux"
system: "ubuntu/12.04/x86_64"
rvm:
version: "rvm 1.25.24 (stable) ..."
ruby:
interpreter: "ruby"
version: "2.1.1p76"
date: "2014-02-24"
platform: "x86_64-linux"
patchlevel: "2014-02-24 revision 45161"
full_version: "ruby 2.1.1p76 (2014-02-24 revision 45161) [x86_64-linux]"

Bug also can be reproduced with linux ruby 2.0.0 (ruby 2.0.0p451 (2014-02-24 revision 45167) [x86_64-linux]) and windows ruby 2.0.0 (ruby 2.0.0p451 (2014-02-24) [i386-mingw32]). Other versions and platforms were not tested.

History

#1 Updated by Valentin Syrovatskiy about 1 year ago

More accurate description: Array#bsearch cannot find first match while using block with equality condition:

Example:
$ irb
2.1.1 :001 > [1, 2].bsearch{|x| x == 1}
=> nil
(WRONG, expected 1)
2.1.1 :002 > [1, 2].bsearch{|x| x > 0}
=> 1
(Correct)

#2 Updated by Yusuke Endoh about 1 year ago

  • Status changed from Open to Rejected

Array#bsearch is binary search; it works correctly only when the array is sorted.
In other words, "ary.map { cond }" must return [false, false, ..., false, true, true, ..., true] if you want to use "ary.bsearch { cond }".

[{a:1, b:2}, {a:3, b:4}].bsearch{|x| x[:a] == 1}

NG, [{a:1, b:2}, {a:3, b:4}].map {|x| x[:a] == 1 } returns [true, false].

[{a:3, b:4}, {a:1, b:2}].bsearch{|x| x[:a] == 1}

OK, [{a:3, b:4}, {a:1, b:2}].map {|x| x[:a] == 1} returns [false, true].

[{a:3, b:4}, {a:1, b:2}].bsearch{|x| x[:a] == 3}

NG, [{a:3, b:4}, {a:1, b:2}].map {|x| x[:a] == 3} returns [true, false].

[{a:3, b:4}, {a:1, b:2}].bsearch{|x| x[:b] == 4}

NG, [{a:3, b:4}, {a:1, b:2}].map {|x| x[:b] == 4} returns [true, false].

[{a:3, b:4}, {a:1, b:2}, {a:3, b:5}].bsearch{|x| x[:a] == 3}

NG, [{a:3, b:4}, {a:1, b:2}, {a:3, b:5}].map {|x| x[:a] == 3} returns [true, false, true].

You should use Enumerable#find for your cases.

Yusuke Endoh mame@tsg.ne.jp

#3 Updated by Valentin Syrovatskiy about 1 year ago

.

Understood. Thanks for explanation.

Also available in: Atom PDF