Какие числа X между?

Question

Учитывая массив, такой как [10,42,45,45,61,61,75,90,1240], как мне найти, какие числа X находится между? Например, если X = 59, ответы будут [45,45,61,61].

Кажется, что для этого идеально подойдет перечислитель select, но я не могу понять, как выбрать все элементы с обеих сторон.

Answer 1

Вам, кажется, нужны повторные значения границ, не так ли? Вот функциональный подход в качестве примера. Это O (n), поэтому, как отмечают другие, лучше использовать алгоритм деления пополам O (log (n)), если у вас большие входные массивы (примечание: проверяемое значение должно быть между xs.min и xs.max):

xs = [10,42,45,45,61,61,75,90,1240]
chk_pairs = xs.chunk { |x| x }.each_cons(2)
boundaries = chk_pairs.detect { |_, (y, ys)| y > 59 }.flat_map { |x, xs| xs }
#=> [45, 45, 61, 61]

Answer 2

Предполагая, что ваш входной массив всегда сортируется (как ваш образец), вы можете найти следующие более низкие и более высокие (или, возможно, равные) числа, используя двоичный поиск. В вашем конкретном случае вы бы, очевидно, посмотрели налево и направо оттуда, чтобы найти все числа, равные следующему нижнему / большему, которое вы изначально нашли.