ruby bsearch, find last occurrence

Question

Is there a way to make bsearch return the last occurrence instead of the first?

For example:

arr = [1,2,3,4,4,5]
arr.bsearch { |x| 4 - x } # this returns the first 4

hash = {
  1 => {
    "foo" => "bar",
    "test" => "abc"
  },
  4 => {
    "foo" => "bar2",
    "test2" => "def"
  },
  5 => {
    "test2" => "abc"
  }
}

hash.keys.bsearch { |x| !hash[x]['test2'].nil? } # this returns 4, but I want it to return 5

I want to find the last occurrence where 'test'2 is not empty.

Out of curiosity, why do you want the last occurrence of an element if they are identical? — supersam654, Sep 20 '19 at 01:13
If you wish to find last key `k` of `hash` for which `arr.include?(k) #=> true` and `hash[k].key?("test2") #=> true`, try this: `(arr & hash.keys).reverse_each.find { |k| hask[k].key?("test2") }`. That doesn't have anything to do with `bsearch`, however, so I guess I don't understand your question. Please clarify. — Cary Swoveland, Sep 20 '19 at 02:09

score 0 · Answer 1 · answered Sep 20 '19 at 05:59

0

You can try this Here in variable y we will store the last occurrence..

hash.keys.bsearch { |x| y = x if !hash[x]['test2'].nil? }

answered Sep 20 '19 at 05:59

Karan Bamniya

93
1
7

BobRodes · Answer 2 · 2019-09-20T06:07:00.250

0

You can reverse the hash and run bsearch against it. With your hash:

hash.reverse_each.to_h.keys.bsearch { |x| !hash[x]['test2'].nil? }
=> 5

This post will shed some light on how bsearch works.

edited Sep 20 '19 at 06:07

answered Sep 20 '19 at 06:01

BobRodes

5,990
2
24
26

Amadan · Answer 3 · 2019-09-20T06:30:48.550

bsearch in the form you are using (taking a block that yields integers) does not return the first of the identical values; it returns any that it stumbles upon, as it thinks they're identical. For example:

[1, 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7, 3, 4, 5].bsearch { |e| 2 - e.to_i }
# => 2.5

The returned value is somewhere in the middle of the 2.x values, simply because bsearch stumbled upon it first. If you want to return the first value, you have to use the alternate form, where the block yields booleans. From there, it is trivial to rework it for last. For example:

array = [1, 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7, 3, 4, 5]
indices = array.size.times.to_a
first_index = indices.bsearch { |i| array[i].to_i >= 2 }
last_index = indices.reverse.bsearch { |i| array[i].to_i <= 2 }
array[first_index..last_index]
# => [2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7]

If you don't need indices but the first and last element themselves, then this suffices:

first_element = array.bsearch { |e| e.to_i >= 2 }
last_element = array.reverse.bsearch { |e| e.to_i <= 2 }

For the hash part of the question though, your question is strange. For bsearch form where the block yields a boolean (as you're using in that example), it is mandatory that the block yields false for any element before the one you search, and true thereafter. (Similarly, when block yields integers, it should return negative values followed by zeroes followed by positive values. In other words, the array is supposed to be sorted with respect to the predicate being searched for.) So by definition, the last element that fits your criterion (all elements without "test1" are before all elements with "test1") must be hash.values.last.

ruby bsearch, find last occurrence

3 Answers3