前回の答えの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"