bin.rb

gistfile1.rb

# Дано: массив случайных натуральных чисел X в случайном порядке, среди которых могут быть дубликаты. Целое число C.
# Вопрос: может ли число C быть сформировано суммой двух элементов массива? Другими словами, существуют ли такие i, j,
# что X[i] + X[j] == C? Знать нам эти числа не обязательно, достаточно знать, что такие числа есть.
# Очевидным способом ответ ищется за O(n^2). Требуется найти более быстрое асимптотически решение.
# Исходный массив (X) записан в файл построчно, целевая сумма (C) либо передаётся параметром, либо жёстко забита в код.
# В помощь предлагается специально подготовленный файл на 100 000 чисел и ниже перечислено несколько тестовых чисел с
# правильными ответами - тут можно проверять решение. Кстати, квадратичные решения на 100 000 на моём компьютере в Руби
# работают порядка 40 минут, так что стимул решить правильно вроде бы есть.
# Тестовые примеры с ответами. Файл на 100 000 чисел в аттаче.

class Search
  def self.binary_search(*arr, item)
    arr = arr[0].sort
    return nil if item.nil?
    low = 0
    high = arr.size - 1
    while low <= high
      mid = (low + high) / 2
      val = arr[mid]
      if val > item
        high = mid - 1
      elsif val < item
        low = mid + 1
      else
        return val
      end
    end
    nil
  end
end

class Find < Search
  def self.start(number)
    arr=[]; newarr=[];
    File.foreach('input.txt').map { |line| line.split(" ") }.each{|x| arr << x[0].to_i}

    arr.each do |x|
      newarr << number - x

      newarr.each do |y|
        break if Search.binary_search(arr, y) && number == x + y
      end
    end
    p 'found'
  end
end

Find.start(884492)