bisection_search.rb

# Search who cause the test function succeed from candidates
#
# @param [Array<T>] array of candidates
# @param [(Array<T>) -> bool] lambda function to test subset of candidates
# @return [T] last survivor against test function
def bisection_search(candidates, test)
  loop do
    head = candidates[0...candidates.length/2]
    tail = candidates - head
    
    head_ok = test.call(head)
    tail_ok = test.call(tail)
    
    if head_ok && tail_ok
      raise <<~EOM
        both targets succeeded
          A = #{head}
          B = #{tail}
        EOM
    elsif head_ok
      if head.length == 1
        return head.first
      else
        candidates = head
      end
    elsif tail_ok
      if tail.length == 1
        return tail.first
      else
        candidates = tail
      end
    else
      raise <<~EOM
        both targets failed
          A = #{head}
          B = #{tail}
        EOM
    end
  end
end

if __FILE__ == $0
  candidates = (0...100).to_a
  p bisection_search(candidates, lambda { |subcandidates| subcandidates.include?(42) }) == 42
end