ruby bsearch, найти последнее вхождение

Question

Есть ли способ заставить bsearch вернуть последнее вхождение вместо первого?

Например:

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

Я хочу найти последнее вхождение, где 'test'2 не пусто.

Answer 1

Вы можете изменить хеш и запустить bsearch против него.С вашим хешем:

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

Этот пост проливает свет на то, как работает bsearch.

Answer 2

bsearch в используемой вами форме (принимая блок, который выдает целые числа) не возвращает первое из идентичных значений;он возвращает все, на что наткнулся, так как думает, что они идентичны.Например:

[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

Возвращенное значение находится где-то посередине значений 2.x, просто потому, что bsearch наткнулся на него первым.Если вы хотите вернуть первое значение, вы должны использовать альтернативную форму, где блок дает логические значения.Оттуда, это тривиально, чтобы переделать его для последнего.Например:

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]

Если вам нужны не индексы, а сами первый и последний элементы, то этого достаточно:

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

---

Для хэш-части вопросахотя ваш вопрос странный.Для формы bsearch, где блок выдает логическое значение (как вы используете в этом примере), обязательно, чтобы блок выдал false для любого элемента перед тем, который вы ищете, и true после.(Точно так же, когда блок возвращает целые числа, он должен возвращать отрицательные значения, за которыми следуют нули, за которыми следуют положительные значения. Другими словами, предполагается, что массив должен быть отсортирован относительно искомого предиката.) Таким образом, по определению, последний элемент, которыйсоответствует вашему критерию (все элементы без "test1" предшествуют всем элементам с "test1") должен быть hash.values.last.

Answer 3

Вы можете попробовать это Здесь в переменной y мы будем хранить последнее вхождение ..

hash.keys.bsearch {| x |y = x, если! hash [x] ['test2']. nil?}