Binary search

Binary search is a search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array. Therefore, if they are unequal, the search continues on the remaining half until it is successful or the remaining half is empty.

Solutions A and B are explanations to the Binary Search described above. Choose the solution that gives a faster output and explain why.

Solution A
def iterative_bsearch(a, value)
  low, hi = get_limits(a)
  while low < hi
    mid = (low + hi) / 2
    if a[mid] == value
      return mid
    elsif a[mid] < value
      low = mid + 1
    else
      hi = mid
    end
  end
  false
end
 
Solution B
def recursive_bsearch(a, value)
  low, hi = get_limits(a)
  if low >= hi
    return false
  end
  mid = (low + hi) / 2
  if a[mid] == value
    mid
  elsif a[mid] < value
    recursive_bsearch(a[(mid+1)..hi], value)
  else
    recursive_bsearch(a[low..mid], value)
  end
end
def get_limits(a)
  [0, a.length - 1]
end
 
Log in to accept this challenge
Submitted by others
  • As the function naming implies, solution A is "iterative", and solution B is "recursive". I choose solution A as the better performer because iteration is usually faster than its recursive counterpart.

    http://stackoverflow.com/questions/15688019/recursion-versus-iteration gives a nice description of why that is the case (in short, recursion needs to perform more memory allocation).

    The existence of tail call optimisation in the language could speak in favor of recursion, but according to this SO post, you can't rely on Ruby to do tail call optimisations.

    1
    reply
    • But, is solution A not just fast but precise as well?

  • As there are two solutions are given, I choose first one which is iterative as it required less space and faster then its recursive counter part