プログラミングコンテストチャレンジブック演習「くじ引き」2

前回の答えのbinarySearchを再帰呼び出しを使って書き直してみました。
でもあまりすっきりしない。むう。
このお題を解いている時に知ったんですが、RubyのArrayに標準で付いている検索メソッド（Index）は線形探索で実装されているらしいです。
http://d.hatena.ne.jp/mkgin/20100117/1263688390
まあ確かにソートされてるかどうか、どんな型のデータが入ってるかわからないので二分探索はできないんでしょうが、そうするとRubyで二分探索をする場合は自分で実装しないといけないってこと？

$kuji = [1, 2, 3, 4, 10, 30, 2]
N = $kuji.length - 1
m = 100

def GetAllKcKdConbination()
  kujiSubset = Array.new
  for i in 0..N
    for j in i..N
      kujiSubset.push($kuji[i] + $kuji[j])
    end
  end
  return kujiSubset.sort
end

def binarySearch(target, array, high, low)
  return false if high - low == 0
  pos = ((low + high) / 2).truncate
  if array[pos] == target then return true
  elsif array[pos] < target then return binarySearch(target, array, high, pos + 1)
  else return binarySearch(target, array, pos - 1, low)
  end
end

allKcKd = GetAllKcKdConbination()

for i in 0..N
  for j in 0..N
    if binarySearch(m - $kuji[i] - $kuji[j], allKcKd, allKcKd.length - 1, 0)
      puts "YES"
      exit(0)
    end
  end
end

puts "NO"