2015-12-14 1 views
-5
ary = [1, 4, 6, 9] 
(0...ary.size).bsearch { |i| 
    ary[i] - 1 
}         # => nil 

1 - ary[i]       # => 0 

Когда код написан в форме ary[i] - 1, которая не работает должным образом.Обратное выражение в блоке bsearch не работает

Что я пытаюсь сделать, так это найти индекс числа 1 в массиве.

Но 1 - ary[i] может правильно вернуть индекс номера. Почему не работает ary[i] - 1?

+0

Он работает так, как он предназначен для работы - пожалуйста, прочитайте - http: // ruby-doc.org/core-2.2.0/Array.html # method-i-bsearch Пожалуйста, уточните, что вы пытаетесь достичь –

+0

Я читал документ, но тест 'ary [i] - 1' должен возвращать 0, но он возвращает нуль. Я до сих пор этого не понимаю. – canoe

+1

Какова цель вашего кода? Чего вы пытаетесь достичь? –

ответ

3

Array#bsearch предназначен для выполнения бинарного поиска, чтобы найти элемент, соответствующий определенным критериям. Согласно documentation, если вы возвращаете числовые значения из блока, используется тип поиска find-any mode.

Поиск начинается с центра сортированного массива - и если блок возвращает отрицательное значение, он продолжает поиск в первой половине, а если блок возвращает положительное значение, он продолжает поиск во второй половине массива.

В вашем случае, когда вы используете ary[i] - 1, значение, возвращаемое блоком, всегда положительное и поиск продолжается рекурсивно на второй половине массива - и никогда не находит значение 1.

Вот код, с некоторыми отладочные:

ary = [1, 4, 6, 9] 
p (0...ary.size).bsearch { |i| 
    puts "Elem: #{ary[i]} Index: #{i}" 
    ary[i] - 1 
} 

Выход:

Elem: 4 Index: 1 
Elem: 6 Index: 2 
Elem: 9 Index: 3 
nil 
[Finished in 0.4s]  
2

Array#bsearch возвращает элемент массива, а не индекс соответствующего элемента.

Вместо этого вы можете использовать Array#index.

+1

Ruby 2.3 имеет 'Array # bsearch_index'. – sawa

1

Если вы хотите, чтобы найти индекс элемента вместо самого элемента, вы должны использовать Array#bsearch_index , Примечание: этот метод был введен в Ruby 2.3, который на момент написания этой статьи еще не выпущен (он будет выпущен на Рождество 2015 года).

feature request для Array#bsearch_index содержит comment от Юсукэ ЭндоН, показывающий, как реализовать Array#bsearch_index (и на самом деле Array#bsearch, а) на основе Range#bsearch:

class Array 
    def bsearch_index(&blk) 
    return enum_for(__method__) unless blk 
    (0...size).bsearch {|i| yield self[i] } 
    end 
end 

Когда либо работает Рубин 2.3 или с использованием указанной выше обезьяны патч, то вы можете сделать:

ary.bsearch_index(&1.method(:-)) 

для того, чтобы найти индекс 1 элемента в массиве.

Причина, почему он не работает с

ary.bsearch_index {|el | el - 1 } 

проста: блок нарушает договор bsearch_index (а также bsearch, так как они одинаковы). Блок должен вернуть положительное число для индексов слева от того, которое вы ищете, отрицательное число для индексов справа от того, которое вы ищете, и 0 для индексов в пределах диапазона, который вы ищете. Ваш блок делает наоборот.